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 \
#include "flow.h"
#include "hash.h"
#include "rculist.h"
-#include "tag.h"
/* Classifier internal definitions, subject to change at any time. */
* 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'
/* '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.
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
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
classifier_destroy(struct classifier *cls)
{
if (cls) {
- struct cls_partition *partition;
struct cls_subtable *subtable;
int i;
}
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);
}
}
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. */
{
/* 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]);
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
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;
uint32_t basis = 0, hash, ihash[CLS_MAX_INDICES];
}
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 {
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. */
* 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]);
&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,
}
*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);
+++ /dev/null
-/*
- * 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);
- }
- }
-}
+++ /dev/null
-/*
- * 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;
-}
-\f
-/* 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 */