/* Accessed by all readers. */
struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */
- /* Controls rule's visibility to lookups.
+ /* Rule versioning.
*
- * When 'visibility' is:
- *
- * > 0 - rule is visible starting from version 'visibility'
- * <= 0 - rule is invisible starting from version '-(visibility)'
- *
- * The minimum version number used in lookups is 1 (== CLS_NO_VERSION),
- * which implies that when 'visibility' is:
- *
- * 1 - rule is visible in all lookup versions
- * 0 - rule is invisible in all lookup versions. */
- atomic_llong visibility;
+ * CLS_NOT_REMOVED_VERSION has a special meaning for 'remove_version',
+ * meaningthat the rule has been added but not yet removed.
+ */
+ const cls_version_t add_version; /* Version rule was added in. */
+ ATOMIC(cls_version_t) remove_version; /* Version rule is removed in. */
const struct cls_rule *cls_rule;
const struct miniflow flow; /* Matching rule. Mask is in the subtable. */
void cls_match_free_cb(struct cls_match *);
static inline void
-cls_match_set_visibility(struct cls_match *rule, long long version)
+cls_match_set_remove_version(struct cls_match *rule, cls_version_t version)
{
- atomic_store_relaxed(&rule->visibility, version);
+ atomic_store_relaxed(&rule->remove_version, version);
}
static inline bool
-cls_match_visible_in_version(const struct cls_match *rule, long long version)
+cls_match_visible_in_version(const struct cls_match *rule,
+ cls_version_t version)
{
- long long visibility;
+ cls_version_t remove_version;
/* C11 does not want to access an atomic via a const object pointer. */
- atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->visibility,
- &visibility);
-
- if (OVS_LIKELY(visibility > 0)) {
- /* Rule is visible starting from version 'visibility'. */
- return version >= visibility;
- } else {
- /* Rule is invisible starting from version '-visibility'. */
- return version < -visibility;
- }
+ atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->remove_version,
+ &remove_version);
+
+ return rule->add_version <= version && version < remove_version;
}
static inline bool
cls_match_is_eventually_invisible(const struct cls_match *rule)
{
- long long visibility;
+ cls_version_t remove_version;
/* C11 does not want to access an atomic via a const object pointer. */
- atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->visibility,
- &visibility);
+ atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->remove_version,
+ &remove_version);
- return visibility <= 0;
+ return remove_version <= CLS_MAX_VERSION;
}
\f
ovsrcu_init(&cls_match->next, NULL);
*CONST_CAST(const struct cls_rule **, &cls_match->cls_rule) = rule;
*CONST_CAST(int *, &cls_match->priority) = rule->priority;
- atomic_init(&cls_match->visibility, 0); /* Initially invisible. */
+ *CONST_CAST(cls_version_t *, &cls_match->add_version) = rule->version;
+ atomic_init(&cls_match->remove_version, rule->version); /* Initially
+ invisible. */
miniflow_clone_inline(CONST_CAST(struct miniflow *, &cls_match->flow),
&rule->match.flow, count);
ovsrcu_set_hidden(&cls_match->conj_set,
static void destroy_subtable(struct classifier *cls, struct cls_subtable *);
static const struct cls_match *find_match_wc(const struct cls_subtable *,
- long long version,
+ cls_version_t version,
const struct flow *,
struct trie_ctx *,
unsigned int n_tries,
* versioning is used at most one of them is ever visible for lookups on any
* given 'version'. */
static inline const struct cls_match *
-next_visible_rule_in_list(const struct cls_match *rule, long long version)
+next_visible_rule_in_list(const struct cls_match *rule, cls_version_t version)
{
do {
rule = cls_match_next(rule);
- if (!rule) {
- /* We have reached the head of the list, stop. */
- break;
- }
- } while (!cls_match_visible_in_version(rule, version));
+ } while (rule && !cls_match_visible_in_version(rule, version));
return rule;
}
static inline void
cls_rule_init__(struct cls_rule *rule, unsigned int priority,
- long long version)
+ cls_version_t version)
{
- ovs_assert(version > 0);
-
rculist_init(&rule->node);
*CONST_CAST(int *, &rule->priority) = priority;
- *CONST_CAST(long long *, &rule->version) = version;
+ *CONST_CAST(cls_version_t *, &rule->version) = version;
rule->cls_match = NULL;
}
* 0 and UINT16_MAX, inclusive.) */
void
cls_rule_init(struct cls_rule *rule, const struct match *match, int priority,
- long long version)
+ cls_version_t version)
{
cls_rule_init__(rule, priority, version);
minimatch_init(CONST_CAST(struct minimatch *, &rule->match), match);
void
cls_rule_init_from_minimatch(struct cls_rule *rule,
const struct minimatch *match, int priority,
- long long version)
+ cls_version_t version)
{
cls_rule_init__(rule, priority, version);
minimatch_clone(CONST_CAST(struct minimatch *, &rule->match), match);
* The caller must eventually destroy 'dst' with cls_rule_destroy(). */
void
cls_rule_clone_in_version(struct cls_rule *dst, const struct cls_rule *src,
- long long version)
+ cls_version_t version)
{
cls_rule_init__(dst, src->priority, version);
minimatch_clone(CONST_CAST(struct minimatch *, &dst->match), &src->match);
*
* 'rule_' must be in a classifier. */
void
-cls_rule_make_invisible_in_version(const struct cls_rule *rule_,
- long long version, long long lookup_version)
-{
- struct cls_match *rule = rule_->cls_match;
-
- /* XXX: Adjust when versioning is actually used. */
- ovs_assert(version >= rule_->version && version >= lookup_version);
-
- /* Normally, we call this when deleting a rule that is already visible to
- * lookups. However, sometimes a bundle transaction will add a rule and
- * then delete it before the rule has ever become visible. If we set such
- * a rule to become invisible in a future 'version', it would become
- * visible to all prior versions. So, in this case we must set the rule
- * visibility to 0 (== never visible). */
- if (cls_match_visible_in_version(rule, lookup_version)) {
- /* Make invisible starting at 'version'. */
- atomic_store_relaxed(&rule->visibility, -version);
- } else {
- /* Rule has not yet been visible to lookups, make invisible in all
- * version. */
- atomic_store_relaxed(&rule->visibility, 0);
- }
+cls_rule_make_invisible_in_version(const struct cls_rule *rule,
+ cls_version_t remove_version)
+{
+ ovs_assert(remove_version >= rule->cls_match->add_version);
+
+ cls_match_set_remove_version(rule->cls_match, remove_version);
}
/* This undoes the change made by cls_rule_make_invisible_after_version().
void
cls_rule_restore_visibility(const struct cls_rule *rule)
{
- atomic_store_relaxed(&rule->cls_match->visibility, rule->version);
+ cls_match_set_remove_version(rule->cls_match, CLS_NOT_REMOVED_VERSION);
}
/* Return true if 'rule' is visible in 'version'.
*
* 'rule' must be in a classifier. */
bool
-cls_rule_visible_in_version(const struct cls_rule *rule, long long version)
+cls_rule_visible_in_version(const struct cls_rule *rule, cls_version_t version)
{
return cls_match_visible_in_version(rule->cls_match, version);
}
uint32_t hash;
int i;
- ovs_assert(rule->version > 0);
-
/* 'new' is initially invisible to lookups. */
new = cls_match_alloc(rule, conjs, n_conjs);
/* No change in subtable's max priority or max count. */
/* Make 'new' visible to lookups in the appropriate version. */
- cls_match_set_visibility(new, rule->version);
+ cls_match_set_remove_version(new, CLS_NOT_REMOVED_VERSION);
/* Make rule visible to iterators (immediately). */
rculist_replace(CONST_CAST(struct rculist *, &rule->node),
}
/* Make 'new' visible to lookups in the appropriate version. */
- cls_match_set_visibility(new, rule->version);
+ cls_match_set_remove_version(new, CLS_NOT_REMOVED_VERSION);
/* Make rule visible to iterators (immediately). */
rculist_push_back(&subtable->rules_list,
* 'flow' is non-const to allow for temporary modifications during the lookup.
* Any changes are restored before returning. */
static const struct cls_rule *
-classifier_lookup__(const struct classifier *cls, long long version,
+classifier_lookup__(const struct classifier *cls, cls_version_t version,
struct flow *flow, struct flow_wildcards *wc,
bool allow_conjunctive_matches)
{
* 'flow' is non-const to allow for temporary modifications during the lookup.
* Any changes are restored before returning. */
const struct cls_rule *
-classifier_lookup(const struct classifier *cls, long long version,
+classifier_lookup(const struct classifier *cls, cls_version_t version,
struct flow *flow, struct flow_wildcards *wc)
{
return classifier_lookup__(cls, version, flow, wc, true);
const struct cls_rule *
classifier_find_match_exactly(const struct classifier *cls,
const struct match *target, int priority,
- long long version)
+ cls_version_t version)
{
const struct cls_rule *retval;
struct cls_rule cr;
* first matching cls_rule via '*pnode', or NULL if there are no matches.
*
* - If 'target' is null, or if the 'target' is a catchall target and the
- * target's version is CLS_NO_VERSION, the cursor will visit every rule
+ * target's version is CLS_MAX_VERSION, the cursor will visit every rule
* in 'cls' that is not invisible in any version.
*
* - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls'
}
static inline const struct cls_match *
-find_match(const struct cls_subtable *subtable, long long version,
+find_match(const struct cls_subtable *subtable, cls_version_t version,
const struct flow *flow, uint32_t hash)
{
const struct cls_match *head, *rule;
}
static const struct cls_match *
-find_match_wc(const struct cls_subtable *subtable, long long version,
+find_match_wc(const struct cls_subtable *subtable, cls_version_t version,
const struct flow *flow, struct trie_ctx trie_ctx[CLS_MAX_TRIES],
unsigned int n_tries, struct flow_wildcards *wc)
{
* invisible to lookups. This means that lookups won't find the rule, but the
* rule is immediately available to classifier iterations.
*
- * Similarly, a rule can be marked as to be deleted in a future version, or
- * more precisely, to be visible upto a given version number. To delete a rule
- * in a way to not remove the rule before all ongoing lookups are finished, the
- * rule should be marked as "to be deleted" by setting the rule's visibility to
- * the negation of the last version number in which it should be visible.
+ * Similarly, a rule can be marked as to be deleted in a future version. To
+ * delete a rule in a way to not remove the rule before all ongoing lookups are
+ * finished, the rule should be made invisible in a specific version number.
* Then, when all the lookups use a later version number, the rule can be
- * actually deleted from the classifier. A rule that is marked for deletion
- * after a future version will not appear in iterations, although it will still
- * be found by lookups using a lookup version number up to that future version
- * number.
+ * actually removed from the classifier.
*
* Classifiers can hold duplicate rules (rules with the same match criteria and
- * priority) when at most one of the duplicates with the same priority is
- * visible in any given lookup version. The caller responsible for classifier
- * modifications must maintain this invariant.
+ * priority) when at most one of these duplicates is visible in any given
+ * lookup version. The caller responsible for classifier modifications must
+ * maintain this invariant.
*
* The classifier supports versioning for two reasons:
*
#include "meta-flow.h"
#include "pvector.h"
#include "rculist.h"
+#include "type-props.h"
#ifdef __cplusplus
extern "C" {
rcu_trie_ptr root; /* NULL if none. */
};
+typedef uint64_t cls_version_t;
+
+#define CLS_MIN_VERSION 0 /* Default version number to use. */
+#define CLS_MAX_VERSION (TYPE_MAXIMUM(cls_version_t) - 1)
+#define CLS_NOT_REMOVED_VERSION TYPE_MAXIMUM(cls_version_t)
+
enum {
- CLS_MIN_VERSION = 1, /* Default version number to use. */
- CLS_MAX_VERSION = LLONG_MAX, /* Last possible version number. */
CLS_MAX_INDICES = 3, /* Maximum number of lookup indices per subtable. */
CLS_MAX_TRIES = 3 /* Maximum number of prefix trees per classifier. */
};
struct cls_rule {
struct rculist node; /* In struct cls_subtable 'rules_list'. */
const int priority; /* Larger numbers are higher priorities. */
- const long long version; /* Version in which the rule was added. */
+ const cls_version_t version; /* Version in which the rule was added. */
struct cls_match *cls_match; /* NULL if not in a classifier. */
const struct minimatch match; /* Matching rule. */
};
void cls_rule_init(struct cls_rule *, const struct match *, int priority,
- long long version);
+ cls_version_t);
void cls_rule_init_from_minimatch(struct cls_rule *, const struct minimatch *,
- int priority, long long version);
+ int priority, cls_version_t);
void cls_rule_clone(struct cls_rule *, const struct cls_rule *);
void cls_rule_clone_in_version(struct cls_rule *, const struct cls_rule *,
- long long version);
+ cls_version_t);
void cls_rule_move(struct cls_rule *dst, struct cls_rule *src);
void cls_rule_destroy(struct cls_rule *);
bool cls_rule_is_catchall(const struct cls_rule *);
bool cls_rule_is_loose_match(const struct cls_rule *rule,
const struct minimatch *criteria);
-bool cls_rule_visible_in_version(const struct cls_rule *, long long version);
+bool cls_rule_visible_in_version(const struct cls_rule *, cls_version_t);
void cls_rule_make_invisible_in_version(const struct cls_rule *,
- long long version,
- long long lookup_version);
+ cls_version_t);
void cls_rule_restore_visibility(const struct cls_rule *);
/* Constructor/destructor. Must run single-threaded. */
/* Lookups. These are RCU protected and may run concurrently with modifiers
* and each other. */
const struct cls_rule *classifier_lookup(const struct classifier *,
- long long version, struct flow *,
+ cls_version_t, struct flow *,
struct flow_wildcards *);
bool classifier_rule_overlaps(const struct classifier *,
const struct cls_rule *);
const struct cls_rule *classifier_find_match_exactly(const struct classifier *,
const struct match *,
int priority,
- long long version);
+ cls_version_t);
bool classifier_is_empty(const struct classifier *);
int classifier_count(const struct classifier *);
\f
const struct xbridge *xbridge;
/* Flow tables version at the beginning of the translation. */
- long long tables_version;
+ cls_version_t tables_version;
/* Flow at the last commit. */
struct flow base_flow;
const struct xport *peer = xport->peer;
struct flow old_flow = ctx->xin->flow;
bool old_was_mpls = ctx->was_mpls;
- long long old_version = ctx->tables_version;
+ cls_version_t old_version = ctx->tables_version;
enum slow_path_reason special;
struct ofpbuf old_stack = ctx->stack;
union mf_subvalue new_stack[1024 / sizeof(union mf_subvalue)];
struct ofproto up;
struct dpif_backer *backer;
- atomic_llong tables_version; /* Version # to use in classifier lookups. */
+ ATOMIC(cls_version_t) tables_version; /* For classifier lookups. */
uint64_t dump_seq; /* Last read of udpif_dump_seq(). */
}
static void
-set_tables_version(struct ofproto *ofproto_, long long version)
+set_tables_version(struct ofproto *ofproto_, cls_version_t version)
{
struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
ovs_mutex_unlock(&rule->up.mutex);
}
-long long
+cls_version_t
ofproto_dpif_get_tables_version(struct ofproto_dpif *ofproto OVS_UNUSED)
{
- long long version;
+ cls_version_t version;
atomic_read_relaxed(&ofproto->tables_version, &version);
* 'flow' is non-const to allow for temporary modifications during the lookup.
* Any changes are restored before returning. */
static struct rule_dpif *
-rule_dpif_lookup_in_table(struct ofproto_dpif *ofproto, long long version,
+rule_dpif_lookup_in_table(struct ofproto_dpif *ofproto, cls_version_t version,
uint8_t table_id, struct flow *flow,
struct flow_wildcards *wc, bool take_ref)
{
* 'flow' is non-const to allow for temporary modifications during the lookup.
* Any changes are restored before returning. */
struct rule_dpif *
-rule_dpif_lookup_from_table(struct ofproto_dpif *ofproto, long long version,
- struct flow *flow, struct flow_wildcards *wc,
- bool take_ref, const struct dpif_flow_stats *stats,
+rule_dpif_lookup_from_table(struct ofproto_dpif *ofproto,
+ cls_version_t version, struct flow *flow,
+ struct flow_wildcards *wc, bool take_ref,
+ const struct dpif_flow_stats *stats,
uint8_t *table_id, ofp_port_t in_port,
bool may_packet_in, bool honor_table_miss)
{
bool ofproto_dpif_get_enable_recirc(const struct ofproto_dpif *);
bool ofproto_dpif_get_enable_ufid(struct dpif_backer *backer);
-long long ofproto_dpif_get_tables_version(struct ofproto_dpif *);
+cls_version_t ofproto_dpif_get_tables_version(struct ofproto_dpif *);
struct rule_dpif *rule_dpif_lookup_from_table(struct ofproto_dpif *,
- long long version,
- struct flow *,
+ cls_version_t, struct flow *,
struct flow_wildcards *,
bool take_ref,
const struct dpif_flow_stats *,
long long int eviction_group_timer; /* For rate limited reheapification. */
struct oftable *tables;
int n_tables;
- long long tables_version; /* Controls which rules are visible to
- * table lookups. */
+ cls_version_t tables_version; /* Controls which rules are visible to
+ * table lookups. */
/* Rules indexed on their cookie values, in all flow tables. */
struct hindex cookies OVS_GUARDED_BY(ofproto_mutex);
/* Sets the current tables version the provider should use for classifier
* lookups. */
- void (*set_tables_version)(struct ofproto *ofproto,
- long long version);
+ void (*set_tables_version)(struct ofproto *ofproto, cls_version_t version);
/* ## ---------------- ## */
/* ## ofport Functions ## */
/* ## ---------------- ## */
static void rule_criteria_init(struct rule_criteria *, uint8_t table_id,
const struct match *match, int priority,
- long long version,
+ cls_version_t version,
ovs_be64 cookie, ovs_be64 cookie_mask,
ofp_port_t out_port, uint32_t out_group);
static void rule_criteria_require_rw(struct rule_criteria *,
* supplied as 0. */
static void
rule_criteria_init(struct rule_criteria *criteria, uint8_t table_id,
- const struct match *match, int priority, long long version,
- ovs_be64 cookie, ovs_be64 cookie_mask,
- ofp_port_t out_port, uint32_t out_group)
+ const struct match *match, int priority,
+ cls_version_t version, ovs_be64 cookie,
+ ovs_be64 cookie_mask, ofp_port_t out_port,
+ uint32_t out_group)
{
criteria->table_id = table_id;
cls_rule_init(&criteria->cr, match, priority, version);
if (old_rule) {
/* Mark the old rule for removal in the next version. */
cls_rule_make_invisible_in_version(&old_rule->cr,
- ofproto->tables_version + 1,
- ofproto->tables_version);
+ ofproto->tables_version + 1);
} else {
table->n_flows++;
}
table->n_flows--;
cls_rule_make_invisible_in_version(&rule->cr,
- ofproto->tables_version + 1,
- ofproto->tables_version);
+ ofproto->tables_version + 1);
}
}
tcls_rules[j] = tcls_insert(&tcls, rules[j]);
if (versioned) {
/* Insert the new rule in the next version. */
- *CONST_CAST(long long *, &rules[j]->cls_rule.version)
+ *CONST_CAST(cls_version_t *,
+ &rules[j]->cls_rule.version)
= ++version;
displaced_rule = test_rule_from_cls_rule(
/* Mark the old rule for removal after the current
* version. */
cls_rule_make_invisible_in_version(
- &displaced_rule->cls_rule, version,
- version - 1);
+ &displaced_rule->cls_rule, version);
n_invisible_rules++;
removable_rule = &displaced_rule->cls_rule;
}
/* Mark the rule for removal after the current
* version. */
cls_rule_make_invisible_in_version(
- &rules[j]->cls_rule, version + 1, version);
+ &rules[j]->cls_rule, version + 1);
++version;
n_invisible_rules++;
removable_rule = &rules[j]->cls_rule;
if (versioned) {
/* Mark the rule for removal after the current version. */
cls_rule_make_invisible_in_version(&rules[i]->cls_rule,
- version + 1, version);
+ version + 1);
++version;
n_invisible_rules++;
} else {
if (versioned) {
/* Mark the rule for removal after the current version. */
cls_rule_make_invisible_in_version(&rule->cls_rule,
- version + 1, version);
+ version + 1);
n_removable_rules++;
compare_classifiers(&cls, n_invisible_rules, version,
&tcls);