+++ /dev/null
-/*
- * 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]);
- }
-}
+++ /dev/null
-/*
- * 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;
-}
-\f
-/*
- * 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 */
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. */
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. */
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.
*
/* 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. */
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;
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;
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();
}
}
}
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;
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) {
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();
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;
}
}
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);
}
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;
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;
}
}
/* 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;
{
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;
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;
}
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;
-}
-\f
-/* 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;
- }
- }
-}
\f
static bool
set_frag_handling(struct ofproto *ofproto_,