[ovs-dev] [tags 3/3] tag: Retire the venerable tag library.
Ethan Jackson
ethan at nicira.com
Fri Aug 2 02:08:34 UTC 2013
This patch retires a venerable library whose inception dates before
the first patch of the current repository: tags. They have served us
well, but their time has come for the reasons listed below.
1) They don't actually help much.
In theory, tags had been used to reduce revalidation necessary when
using bonds, mac-learning, and frequently changing flow tables. With
bonds and mac-learning, things change happen so rarely that tagging
isn't worth it. That leaves flow table changes. With the complex flow
tables in my testing, the revalidate_set gets so overwhelmed with
tags, that we end up revalidating every facet every time through the
run loop. In other words, they tags are giving us no benefit.
2) They complicate the code.
This patch simplifies the code and removes a couple of rather ugly
kludges.
3) They complicated locking once threading hits.
Because of the calculate_flow_tag() function, the table_dpif structure
would require locking in a multi-threaded OVS. Though this problem
isn't insurmountable, it's annoying and probably would cause lock
contention.
Of course, we could try to work around these problems with a more
advanced tagging infrastructure, but this moves in the opposite of the
direction we should be. Ideally we'll have a more-or-less stateless
ofproto-dpif supporting a massive number of datapath flows. Tags (or
facets for that matter) aren't going to work in this new world.
Signed-off-by: Ethan Jackson <ethan at nicira.com>
---
lib/automake.mk | 2 -
lib/tag.c | 117 ------------------
lib/tag.h | 134 ---------------------
ofproto/ofproto-dpif-xlate.c | 6 -
ofproto/ofproto-dpif-xlate.h | 2 -
ofproto/ofproto-dpif.c | 272 ++++++------------------------------------
ofproto/ofproto-dpif.h | 5 -
ofproto/ofproto-provider.h | 10 --
ofproto/ofproto.c | 7 --
ofproto/ofproto.h | 1 -
10 files changed, 35 insertions(+), 521 deletions(-)
delete mode 100644 lib/tag.c
delete mode 100644 lib/tag.h
diff --git a/lib/automake.mk b/lib/automake.mk
index f18df91..4cdfcfd 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -191,8 +191,6 @@ lib_libopenvswitch_a_SOURCES = \
lib/svec.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/tag.c b/lib/tag.c
deleted file mode 100644
index f064d17..0000000
--- a/lib/tag.c
+++ /dev/null
@@ -1,117 +0,0 @@
-/*
- * Copyright (c) 2008, 2009, 2010, 2011 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"
-#include <limits.h>
-#include "random.h"
-#include "type-props.h"
-#include "util.h"
-
-#define N_TAG_BITS (CHAR_BIT * sizeof(tag_type))
-BUILD_ASSERT_DECL(IS_POW2(N_TAG_BITS));
-
-#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 randomly selected tag. */
-tag_type
-tag_create_random(void)
-{
- int x, y;
- do {
- uint16_t r = random_uint16();
- x = r & (N_TAG_BITS - 1);
- y = r >> (16 - LOG2_N_TAG_BITS);
- } while (x == y);
- return (1u << x) | (1u << y);
-}
-
-/* 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 'set' as an empty tag set. */
-void
-tag_set_init(struct tag_set *set)
-{
- memset(set, 0, sizeof *set);
-}
-
-static bool
-tag_is_worth_adding(const struct tag_set *set, tag_type tag)
-{
- if (!tag) {
- /* Nothing to add. */
- return false;
- } else if ((set->total & tag) != tag) {
- /* 'set' doesn't have all the bits in 'tag', so we need to add it. */
- return true;
- } else {
- /* We can drop it if some member of 'set' already includes all of the
- * 1-bits in 'tag'. (tag_set_intersects() does a different test:
- * whether some member of 'set' has at least two 1-bit in common with
- * 'tag'.) */
- int i;
-
- for (i = 0; i < TAG_SET_SIZE; i++) {
- if ((set->tags[i] & tag) == tag) {
- return false;
- }
- }
- return true;
- }
-}
-
-/* Adds 'tag' to 'set'. */
-void
-tag_set_add(struct tag_set *set, tag_type tag)
-{
- if (tag_is_worth_adding(set, tag)) {
- /* XXX We could do better by finding the set member to which we would
- * add the fewest number of 1-bits. This would reduce the amount of
- * ambiguity, since e.g. three 1-bits match 3 * 2 / 2 = 3 unique tags
- * whereas four 1-bits match 4 * 3 / 2 = 6 unique tags. */
- tag_type *t = &set->tags[set->n++ % TAG_SET_SIZE];
- *t |= tag;
- if (*t == TYPE_MAXIMUM(tag_type)) {
- set->tags[0] = *t;
- }
-
- set->total |= tag;
- }
-}
-
-/* Adds all the tags in 'other' to 'set'. */
-void
-tag_set_union(struct tag_set *set, const struct tag_set *other)
-{
- size_t i;
-
- for (i = 0; i < TAG_SET_SIZE; i++) {
- tag_set_add(set, other->tags[i]);
- }
-}
diff --git a/lib/tag.h b/lib/tag.h
deleted file mode 100644
index 9d6b4aa..0000000
--- a/lib/tag.h
+++ /dev/null
@@ -1,134 +0,0 @@
-/*
- * Copyright (c) 2008, 2011, 2012 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 "util.h"
-
-/*
- * Tagging support.
- *
- * A 'tag' represents an arbitrary category. Currently, tags are used to
- * represent categories of flows and in particular the dependencies for a flow
- * switching decision. For example, if a flow's output port is based on
- * knowledge that source MAC 00:02:e3:0f:80:a4 is on eth0, then a tag that
- * represents that dependency is attached to that flow in the flowtracking hash
- * table.
- *
- * As this example shows, the universe of possible categories is very large,
- * and even the number of categories that are in use at a given time can be
- * very 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.
- *
- * 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 flowtracking,
- * since we want to be sure that we catch every flow that needs to be
- * revalidated, but it is OK if we revalidate a few extra flows 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. Fortunately, this is not a big
- * problem for us: although there are many flows overall, each individual flow
- * belongs only to a small number of categories.
- */
-
-/* Represents a tag, or the combination of 0 or more tags. */
-typedef uint32_t tag_type;
-
-tag_type tag_create_random(void);
-tag_type tag_create_deterministic(uint32_t seed);
-static inline bool tag_intersects(tag_type, tag_type);
-static inline bool tag_is_valid(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;
-}
-
-/* Returns true if 'tag' is a valid tag, that is, if exactly two bits are set
- * to 1 and the rest to 0. Otherwise, returns false. */
-static inline bool
-tag_is_valid(tag_type tag)
-{
- tag_type x = tag & (tag - 1);
- tag_type y = x & (x - 1);
- return x && !y;
-}
-
-/*
- * A tag set accumulates tags with reduced ambiguity compared to a single tag.
- * The flow tracking uses tag sets to keep track of tags that need to
- * revalidated after a number of packets have been processed.
- */
-#define TAG_SET_SIZE 4
-struct tag_set {
- tag_type total;
- tag_type tags[TAG_SET_SIZE];
- unsigned int n;
-};
-
-void tag_set_init(struct tag_set *);
-void tag_set_add(struct tag_set *, tag_type);
-void tag_set_union(struct tag_set *, const struct tag_set *);
-static inline bool tag_set_is_empty(const struct tag_set *);
-static inline bool tag_set_intersects(const struct tag_set *, tag_type);
-
-/* Returns true if 'set' will match no tags at all,
- * false if it will match at least one tag. */
-static inline bool
-tag_set_is_empty(const struct tag_set *set)
-{
- return !set->n;
-}
-
-/* Returns true if any of the tags in 'tags' are also in 'set',
- * false if the intersection is empty. */
-static inline bool
-tag_set_intersects(const struct tag_set *set, tag_type tags)
-{
- BUILD_ASSERT_DECL(TAG_SET_SIZE == 4);
- return (tag_intersects(set->total, tags)
- && (tag_intersects(set->tags[0], tags)
- || tag_intersects(set->tags[1], tags)
- || tag_intersects(set->tags[2], tags)
- || tag_intersects(set->tags[3], tags)));
-}
-
-#endif /* tag.h */
diff --git a/ofproto/ofproto-dpif-xlate.c b/ofproto/ofproto-dpif-xlate.c
index b665b07..580232e 100644
--- a/ofproto/ofproto-dpif-xlate.c
+++ b/ofproto/ofproto-dpif-xlate.c
@@ -1414,10 +1414,6 @@ xlate_table_action(struct xlate_ctx *ctx,
&ctx->xin->flow, &ctx->xout->wc,
table_id);
- ctx->xout->tags |= calculate_flow_tag(ctx->xbridge->ofproto,
- &ctx->xin->flow, ctx->table_id,
- rule);
-
/* Restore the original input port. Otherwise OFPP_NORMAL and
* OFPP_IN_PORT will have surprising behavior. */
ctx->xin->flow.in_port.ofp_port = old_in_port;
@@ -2193,7 +2189,6 @@ void
xlate_out_copy(struct xlate_out *dst, const struct xlate_out *src)
{
dst->wc = src->wc;
- dst->tags = src->tags;
dst->slow = src->slow;
dst->has_learn = src->has_learn;
dst->has_normal = src->has_normal;
@@ -2269,7 +2264,6 @@ xlate_actions(struct xlate_in *xin, struct xlate_out *xout)
ctx.xin = xin;
ctx.xout = xout;
- ctx.xout->tags = 0;
ctx.xout->slow = 0;
ctx.xout->has_learn = false;
ctx.xout->has_normal = false;
diff --git a/ofproto/ofproto-dpif-xlate.h b/ofproto/ofproto-dpif-xlate.h
index 4cb8530..6c21267 100644
--- a/ofproto/ofproto-dpif-xlate.h
+++ b/ofproto/ofproto-dpif-xlate.h
@@ -21,7 +21,6 @@
#include "ofpbuf.h"
#include "ofproto-dpif-mirror.h"
#include "ofproto-dpif.h"
-#include "tag.h"
struct bfd;
struct bond;
@@ -40,7 +39,6 @@ struct xlate_out {
* set. */
struct flow_wildcards wc;
- tag_type tags; /* Tags associated with actions. */
enum slow_path_reason slow; /* 0 if fast path may be used. */
bool has_learn; /* Actions include NXAST_LEARN? */
bool has_normal; /* Actions output to OFPP_NORMAL? */
diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index 2cf33b2..3c34366 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -85,9 +85,6 @@ static struct rule_dpif *rule_dpif_lookup(struct ofproto_dpif *,
struct flow_wildcards *wc);
static void rule_get_stats(struct rule *, uint64_t *packets, uint64_t *bytes);
-static void rule_invalidate(const struct rule_dpif *);
-static tag_type rule_calculate_tag(const struct flow *,
- const struct minimask *, uint32_t secret);
struct ofbundle {
struct hmap_node hmap_node; /* In struct ofproto's "bundles" hmap. */
@@ -291,7 +288,6 @@ struct ofport_dpif {
struct list bundle_node; /* In struct ofbundle's "ports" list. */
struct cfm *cfm; /* Connectivity Fault Management, if any. */
struct bfd *bfd; /* BFD, if any. */
- tag_type tag; /* Tag associated with this port. */
bool may_enable; /* May be enabled in bonds. */
bool is_tunnel; /* This port is a tunnel. */
long long int carrier_seq; /* Carrier status changes. */
@@ -368,17 +364,6 @@ struct dpif_completion {
struct ofoperation *op;
};
-/* Extra information about a classifier table.
- * Currently used just for optimized flow revalidation. */
-struct table_dpif {
- /* If either of these is nonnull, then this table has a form that allows
- * flows to be tagged to avoid revalidating most flows for the most common
- * kinds of flow table changes. */
- struct cls_table *catchall_table; /* Table that wildcards all fields. */
- struct cls_table *other_table; /* Table with any other wildcard set. */
- uint32_t basis; /* Keeps each table's tags separate. */
-};
-
/* Reasons that we might need to revalidate every facet, and corresponding
* coverage counters.
*
@@ -430,7 +415,6 @@ struct dpif_backer {
/* Facet revalidation flags applying to facets which use this backer. */
enum revalidate_reason need_revalidate; /* Revalidate every facet. */
- struct tag_set revalidate_set; /* Revalidate only matching facets. */
struct hmap drop_keys; /* Set of dropped odp keys. */
bool recv_set_enable; /* Enables or disables receiving packets. */
@@ -496,9 +480,6 @@ struct ofproto_dpif {
struct classifier facets; /* Contains 'struct facet's. */
long long int consistency_rl;
- /* Revalidation. */
- struct table_dpif tables[N_TABLES];
-
/* Support for debugging async flow mods. */
struct list completions;
@@ -706,10 +687,7 @@ type_run(const char *type)
backer->need_revalidate = REV_RECONFIGURE;
}
- if (backer->need_revalidate
- || !tag_set_is_empty(&backer->revalidate_set)) {
- struct tag_set revalidate_set = backer->revalidate_set;
- bool need_revalidate = backer->need_revalidate;
+ if (backer->need_revalidate) {
struct ofproto_dpif *ofproto;
struct simap_node *node;
struct simap tmp_backers;
@@ -776,62 +754,51 @@ type_run(const char *type)
case REV_MAC_LEARNING: COVERAGE_INC(rev_mac_learning); break;
case REV_INCONSISTENCY: COVERAGE_INC(rev_inconsistency); break;
}
-
- if (backer->need_revalidate) {
- /* Clear the drop_keys in case we should now be accepting some
- * formerly dropped flows. */
- drop_key_clear(backer);
- }
-
- /* Clear the revalidation flags. */
- tag_set_init(&backer->revalidate_set);
backer->need_revalidate = 0;
+ /* Clear the drop_keys in case we should now be accepting some
+ * formerly dropped flows. */
+ drop_key_clear(backer);
+
HMAP_FOR_EACH (ofproto, all_ofproto_dpifs_node, &all_ofproto_dpifs) {
struct facet *facet, *next;
+ struct ofport_dpif *ofport;
struct cls_cursor cursor;
+ struct ofbundle *bundle;
if (ofproto->backer != backer) {
continue;
}
- if (need_revalidate) {
- struct ofport_dpif *ofport;
- struct ofbundle *bundle;
-
- xlate_ofproto_set(ofproto, ofproto->up.name, ofproto->ml,
- ofproto->mbridge, ofproto->sflow,
- ofproto->ipfix, ofproto->up.frag_handling,
- ofproto->up.forward_bpdu,
- connmgr_has_in_band(ofproto->up.connmgr),
- ofproto->netflow != NULL,
- ofproto->stp != NULL);
-
- HMAP_FOR_EACH (bundle, hmap_node, &ofproto->bundles) {
- xlate_bundle_set(ofproto, bundle, bundle->name,
- bundle->vlan_mode, bundle->vlan,
- bundle->trunks, bundle->use_priority_tags,
- bundle->bond, bundle->lacp,
- bundle->floodable);
- }
+ xlate_ofproto_set(ofproto, ofproto->up.name, ofproto->ml,
+ ofproto->mbridge, ofproto->sflow,
+ ofproto->ipfix, ofproto->up.frag_handling,
+ ofproto->up.forward_bpdu,
+ connmgr_has_in_band(ofproto->up.connmgr),
+ ofproto->netflow != NULL,
+ ofproto->stp != NULL);
- HMAP_FOR_EACH (ofport, up.hmap_node, &ofproto->up.ports) {
- xlate_ofport_set(ofproto, ofport->bundle, ofport,
- ofport->up.ofp_port, ofport->odp_port,
- ofport->up.netdev, ofport->cfm,
- ofport->bfd, ofport->peer,
- ofport->up.pp.config, ofport->stp_state,
- ofport->is_tunnel, ofport->may_enable);
- }
+ HMAP_FOR_EACH (bundle, hmap_node, &ofproto->bundles) {
+ xlate_bundle_set(ofproto, bundle, bundle->name,
+ bundle->vlan_mode, bundle->vlan,
+ bundle->trunks, bundle->use_priority_tags,
+ bundle->bond, bundle->lacp,
+ bundle->floodable);
+ }
+
+ HMAP_FOR_EACH (ofport, up.hmap_node, &ofproto->up.ports) {
+ xlate_ofport_set(ofproto, ofport->bundle, ofport,
+ ofport->up.ofp_port, ofport->odp_port,
+ ofport->up.netdev, ofport->cfm,
+ ofport->bfd, ofport->peer,
+ ofport->up.pp.config, ofport->stp_state,
+ ofport->is_tunnel, ofport->may_enable);
}
cls_cursor_init(&cursor, &ofproto->facets, NULL);
CLS_CURSOR_FOR_EACH_SAFE (facet, next, cr, &cursor) {
- if (need_revalidate
- || tag_set_intersects(&revalidate_set, facet->xout.tags)) {
- facet_revalidate(facet);
- run_fast_rl();
- }
+ facet_revalidate(facet);
+ run_fast_rl();
}
}
}
@@ -1212,7 +1179,6 @@ open_dpif_backer(const char *type, struct dpif_backer **backerp)
timer_set_duration(&backer->next_expiration, 1000);
backer->need_revalidate = 0;
simap_init(&backer->tnl_backers);
- tag_set_init(&backer->revalidate_set);
backer->recv_set_enable = !ofproto_get_flow_restore_wait();
*backerp = backer;
@@ -1273,7 +1239,6 @@ construct(struct ofproto *ofproto_)
struct shash_node *node, *next;
odp_port_t max_ports;
int error;
- int i;
error = open_dpif_backer(ofproto->up.type, &ofproto->backer);
if (error) {
@@ -1296,14 +1261,6 @@ construct(struct ofproto *ofproto_)
classifier_init(&ofproto->facets);
ofproto->consistency_rl = LLONG_MIN;
- for (i = 0; i < N_TABLES; i++) {
- struct table_dpif *table = &ofproto->tables[i];
-
- table->catchall_table = NULL;
- table->other_table = NULL;
- table->basis = random_uint32();
- }
-
list_init(&ofproto->completions);
ofproto_dpif_unixctl_init();
@@ -1560,11 +1517,8 @@ run(struct ofproto *ofproto_)
hmap_node);
facet = CONTAINER_OF(cr, struct facet, cr);
- if (!tag_set_intersects(&ofproto->backer->revalidate_set,
- facet->xout.tags)) {
- if (!facet_check_consistency(facet)) {
- ofproto->backer->need_revalidate = REV_INCONSISTENCY;
- }
+ if (!facet_check_consistency(facet)) {
+ ofproto->backer->need_revalidate = REV_INCONSISTENCY;
}
}
@@ -1591,9 +1545,6 @@ wait(struct ofproto *ofproto_)
if (ofproto->sflow) {
dpif_sflow_wait(ofproto->sflow);
}
- if (!tag_set_is_empty(&ofproto->backer->revalidate_set)) {
- poll_immediate_wake();
- }
HMAP_FOR_EACH (ofport, up.hmap_node, &ofproto->up.ports) {
port_wait(ofport);
}
@@ -1729,7 +1680,6 @@ port_construct(struct ofport *port_)
port->bundle = NULL;
port->cfm = NULL;
port->bfd = NULL;
- port->tag = tag_create_random();
port->may_enable = true;
port->stp_port = NULL;
port->stp_state = STP_DISABLED;
@@ -4713,9 +4663,7 @@ facet_lookup_valid(struct ofproto_dpif *ofproto, const struct flow *flow)
facet = facet_find(ofproto, flow);
if (facet
- && (ofproto->backer->need_revalidate
- || tag_set_intersects(&ofproto->backer->revalidate_set,
- facet->xout.tags))
+ && ofproto->backer->need_revalidate
&& !facet_revalidate(facet)) {
return NULL;
}
@@ -4862,7 +4810,6 @@ facet_revalidate(struct facet *facet)
}
/* Update 'facet' now that we've taken care of all the old state. */
- facet->xout.tags = xout.tags;
facet->xout.slow = xout.slow;
facet->xout.has_learn = xout.has_learn;
facet->xout.has_normal = xout.has_normal;
@@ -5299,7 +5246,7 @@ complete_operation(struct rule_dpif *rule)
{
struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
- rule_invalidate(rule);
+ ofproto->backer->need_revalidate = REV_FLOW_TABLE;
if (clogged) {
struct dpif_completion *c = xmalloc(sizeof *c);
c->op = rule->up.pending;
@@ -5327,27 +5274,8 @@ static enum ofperr
rule_construct(struct rule *rule_)
{
struct rule_dpif *rule = rule_dpif_cast(rule_);
- struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
- struct rule_dpif *victim;
- uint8_t table_id;
-
rule->packet_count = 0;
rule->byte_count = 0;
-
- table_id = rule->up.table_id;
- victim = rule_dpif_cast(ofoperation_get_victim(rule->up.pending));
- if (victim) {
- rule->tag = victim->tag;
- } else if (table_id == 0) {
- rule->tag = 0;
- } else {
- struct flow flow;
-
- miniflow_expand(&rule->up.cr.match.flow, &flow);
- rule->tag = rule_calculate_tag(&flow, &rule->up.cr.match.mask,
- ofproto->tables[table_id].basis);
- }
-
complete_operation(rule);
return 0;
}
@@ -5520,136 +5448,6 @@ put_userspace_action(const struct ofproto_dpif *ofproto,
return odp_put_userspace_action(pid, cookie, cookie_size, odp_actions);
}
-
-tag_type
-calculate_flow_tag(struct ofproto_dpif *ofproto, const struct flow *flow,
- uint8_t table_id, struct rule_dpif *rule)
-{
- if (table_id > 0 && table_id < N_TABLES) {
- struct table_dpif *table = &ofproto->tables[table_id];
- if (table->other_table) {
- return (rule && rule->tag
- ? rule->tag
- : rule_calculate_tag(flow, &table->other_table->mask,
- table->basis));
- }
- }
-
- return 0;
-}
-
-/* Optimized flow revalidation.
- *
- * It's a difficult problem, in general, to tell which facets need to have
- * their actions recalculated whenever the OpenFlow flow table changes. We
- * don't try to solve that general problem: for most kinds of OpenFlow flow
- * table changes, we recalculate the actions for every facet. This is
- * relatively expensive, but it's good enough if the OpenFlow flow table
- * doesn't change very often.
- *
- * However, we can expect one particular kind of OpenFlow flow table change to
- * happen frequently: changes caused by MAC learning. To avoid wasting a lot
- * of CPU on revalidating every facet whenever MAC learning modifies the flow
- * table, we add a special case that applies to flow tables in which every rule
- * has the same form (that is, the same wildcards), except that the table is
- * also allowed to have a single "catch-all" flow that matches all packets. We
- * optimize this case by tagging all of the facets that resubmit into the table
- * and invalidating the same tag whenever a flow changes in that table. The
- * end result is that we revalidate just the facets that need it (and sometimes
- * a few more, but not all of the facets or even all of the facets that
- * resubmit to the table modified by MAC learning). */
-
-/* Calculates the tag to use for 'flow' and mask 'mask' when it is inserted
- * into an OpenFlow table with the given 'basis'. */
-static tag_type
-rule_calculate_tag(const struct flow *flow, const struct minimask *mask,
- uint32_t secret)
-{
- if (minimask_is_catchall(mask)) {
- return 0;
- } else {
- uint32_t hash = flow_hash_in_minimask(flow, mask, secret);
- return tag_create_deterministic(hash);
- }
-}
-
-/* Following a change to OpenFlow table 'table_id' in 'ofproto', update the
- * taggability of that table.
- *
- * This function must be called after *each* change to a flow table. If you
- * skip calling it on some changes then the pointer comparisons at the end can
- * be invalid if you get unlucky. For example, if a flow removal causes a
- * cls_table to be destroyed and then a flow insertion causes a cls_table with
- * different wildcards to be created with the same address, then this function
- * will incorrectly skip revalidation. */
-static void
-table_update_taggable(struct ofproto_dpif *ofproto, uint8_t table_id)
-{
- struct table_dpif *table = &ofproto->tables[table_id];
- const struct oftable *oftable = &ofproto->up.tables[table_id];
- struct cls_table *catchall, *other;
- struct cls_table *t;
-
- catchall = other = NULL;
-
- switch (hmap_count(&oftable->cls.tables)) {
- case 0:
- /* We could tag this OpenFlow table but it would make the logic a
- * little harder and it's a corner case that doesn't seem worth it
- * yet. */
- break;
-
- case 1:
- case 2:
- HMAP_FOR_EACH (t, hmap_node, &oftable->cls.tables) {
- if (cls_table_is_catchall(t)) {
- catchall = t;
- } else if (!other) {
- other = t;
- } else {
- /* Indicate that we can't tag this by setting both tables to
- * NULL. (We know that 'catchall' is already NULL.) */
- other = NULL;
- }
- }
- break;
-
- default:
- /* Can't tag this table. */
- break;
- }
-
- if (table->catchall_table != catchall || table->other_table != other) {
- table->catchall_table = catchall;
- table->other_table = other;
- ofproto->backer->need_revalidate = REV_FLOW_TABLE;
- }
-}
-
-/* Given 'rule' that has changed in some way (either it is a rule being
- * inserted, a rule being deleted, or a rule whose actions are being
- * modified), marks facets for revalidation to ensure that packets will be
- * forwarded correctly according to the new state of the flow table.
- *
- * This function must be called after *each* change to a flow table. See
- * the comment on table_update_taggable() for more information. */
-static void
-rule_invalidate(const struct rule_dpif *rule)
-{
- struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
-
- table_update_taggable(ofproto, rule->up.table_id);
-
- if (!ofproto->backer->need_revalidate) {
- struct table_dpif *table = &ofproto->tables[rule->up.table_id];
-
- if (table->other_table && rule->tag) {
- tag_set_add(&ofproto->backer->revalidate_set, rule->tag);
- } else {
- ofproto->backer->need_revalidate = REV_FLOW_TABLE;
- }
- }
-}
static bool
set_frag_handling(struct ofproto *ofproto_,
diff --git a/ofproto/ofproto-dpif.h b/ofproto/ofproto-dpif.h
index a094aed..f683281 100644
--- a/ofproto/ofproto-dpif.h
+++ b/ofproto/ofproto-dpif.h
@@ -19,7 +19,6 @@
#include "hmapx.h"
#include "ofproto/ofproto-provider.h"
-#include "tag.h"
#include "timer.h"
#include "util.h"
@@ -45,8 +44,6 @@ struct rule_dpif {
*/
uint64_t packet_count; /* Number of packets received. */
uint64_t byte_count; /* Number of bytes received. */
-
- tag_type tag; /* Caches rule_calculate_tag() result. */
};
static inline struct rule_dpif *rule_dpif_cast(const struct rule *rule)
@@ -85,8 +82,6 @@ bool ofproto_dpif_dscp_from_priority(const struct ofport_dpif *,
uint32_t priority, uint8_t *dscp);
int ofproto_dpif_queue_to_priority(const struct ofproto_dpif *,
uint32_t queue_id, uint32_t *priority);
-tag_type calculate_flow_tag(struct ofproto_dpif *, const struct flow *,
- uint8_t table_id, struct rule_dpif *);
void ofproto_dpif_send_packet_in(struct ofproto_dpif *,
struct ofputil_packet_in *pin);
diff --git a/ofproto/ofproto-provider.h b/ofproto/ofproto-provider.h
index 41d106a..bae789e 100644
--- a/ofproto/ofproto-provider.h
+++ b/ofproto/ofproto-provider.h
@@ -266,7 +266,6 @@ void ofproto_rule_destroy(struct rule *);
bool ofproto_rule_has_out_port(const struct rule *, ofp_port_t out_port);
void ofoperation_complete(struct ofoperation *, enum ofperr);
-struct rule *ofoperation_get_victim(struct ofoperation *);
bool ofoperation_has_out_port(const struct ofoperation *, ofp_port_t out_port);
@@ -918,15 +917,6 @@ struct ofproto_class {
*
* When ->rule_construct() is called, the caller has already inserted
* 'rule' into 'rule->ofproto''s flow table numbered 'rule->table_id'.
- * There are two cases:
- *
- * - 'rule' is a new rule in its flow table. In this case,
- * ofoperation_get_victim(rule) returns NULL.
- *
- * - 'rule' is replacing an existing rule in its flow table that had the
- * same matching criteria and priority. In this case,
- * ofoperation_get_victim(rule) returns the rule being replaced (the
- * "victim" rule).
*
* ->rule_construct() should set the following in motion:
*
diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
index 0625ccf..0417085 100644
--- a/ofproto/ofproto.c
+++ b/ofproto/ofproto.c
@@ -4978,13 +4978,6 @@ ofoperation_complete(struct ofoperation *op, enum ofperr error)
ofopgroup_complete(group);
}
}
-
-struct rule *
-ofoperation_get_victim(struct ofoperation *op)
-{
- ovs_assert(op->type == OFOPERATION_ADD);
- return op->victim;
-}
static uint64_t
pick_datapath_id(const struct ofproto *ofproto)
diff --git a/ofproto/ofproto.h b/ofproto/ofproto.h
index d2756dd..1bde385 100644
--- a/ofproto/ofproto.h
+++ b/ofproto/ofproto.h
@@ -27,7 +27,6 @@
#include "netflow.h"
#include "sset.h"
#include "stp.h"
-#include "tag.h"
#ifdef __cplusplus
extern "C" {
--
1.7.9.5
More information about the dev
mailing list