[ovs-dev] [PATCH v2 7/9] Classifier: Track IP addresses for more wildcarding.
Jarno Rajahalme
jrajahalme at nicira.com
Wed Nov 13 21:32:47 UTC 2013
Add a prefix tree (trie) structure for tracking the used IP address
space, enabling skipping classifier tables containing longer masks
than necessary for the given address. This enables more wildcarding
for datapath flows in ,e.g., parts of the address space without host
routes. In fact, the trie lookups results are only ever used when
they could potentially reduce the number of bits that need to be
un-wildcarded.
The tries are computed before checking any other fields, so the same
tree has nodes also for addresses from mutually exclusive rules,
making this implementation sub-optimal in some cases.
More aggressive table skipping would be possible by maintaining lists
of tables that have prefixes at the lengths encountered on tree
traversal.
Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
lib/classifier.c | 587 ++++++++++++++++++++++++++++++++++++++++++++++++-
lib/classifier.h | 13 ++
lib/flow.c | 12 +-
lib/meta-flow.c | 56 +++++
lib/meta-flow.h | 4 +
lib/ofp-util.h | 2 +-
tests/classifier.at | 2 +-
tests/ofproto-dpif.at | 4 +-
8 files changed, 663 insertions(+), 17 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index 2aec854..026287b 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -27,6 +27,7 @@
#include "packets.h"
#include "ovs-thread.h"
+struct trie_ctx;
static struct cls_subtable *find_subtable(const struct classifier *,
const struct minimask *);
static struct cls_subtable *insert_subtable(struct classifier *,
@@ -43,6 +44,8 @@ static void update_subtables_after_removal(struct classifier *,
static struct cls_rule *find_match(const struct cls_subtable *,
const struct flow *,
+ const struct trie_ctx *,
+ unsigned int n_tries,
struct flow_wildcards *);
static struct cls_rule *find_equal(struct cls_subtable *,
const struct miniflow *, uint32_t hash);
@@ -59,6 +62,19 @@ static struct cls_rule *insert_rule(struct classifier *,
static struct cls_rule *next_rule_in_list__(struct cls_rule *);
static struct cls_rule *next_rule_in_list(struct cls_rule *);
+
+static uint8_t minimask_get_prefix_len(const struct minimask *,
+ const struct mf_field *,
+ unsigned int *);
+static bool trie_lookup(const struct cls_trie *, const struct flow *,
+ struct trie_ctx *);
+static void trie_destroy(struct trie_node *);
+static void trie_insert(struct cls_trie *, const struct cls_rule *);
+static void trie_remove(struct cls_trie *, const struct cls_rule *);
+static void mask_set_prefix_bits(struct flow_wildcards *, uint8_t u32ofs,
+ uint8_t nbits);
+static bool mask_prefix_bits_set(const struct flow_wildcards *,
+ uint8_t u32ofs, uint8_t nbits);
/* cls_rule. */
@@ -153,6 +169,12 @@ cls_rule_is_catchall(const struct cls_rule *rule)
void
classifier_init(struct classifier *cls, const uint8_t *flow_segments)
{
+ int i;
+
+ static enum mf_field_id trie_fields[2] = {
+ MFF_IPV4_DST, MFF_IPV4_SRC
+ };
+
cls->n_rules = 0;
hmap_init(&cls->subtables);
list_init(&cls->subtables_priority);
@@ -165,6 +187,12 @@ classifier_init(struct classifier *cls, const uint8_t *flow_segments)
cls->flow_segments[cls->n_flow_segments++] = *flow_segments++;
}
}
+ for (i = 0; i < sizeof trie_fields / sizeof trie_fields[0]; i++) {
+ cls->tries[i].field = mf_from_id(trie_fields[i]);
+ ovs_assert(cls->tries[i].field);
+ cls->tries[i].root = NULL;
+ }
+ cls->n_tries = i;
}
/* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the
@@ -175,6 +203,13 @@ classifier_destroy(struct classifier *cls)
if (cls) {
struct cls_subtable *partition, *next_partition;
struct cls_subtable *subtable, *next_subtable;
+ int i;
+
+ for (i = 0; i < cls->n_tries; i++) {
+ if (cls->tries[i].root) {
+ trie_destroy(cls->tries[i].root);
+ }
+ }
HMAP_FOR_EACH_SAFE (subtable, next_subtable, hmap_node,
&cls->subtables) {
@@ -271,6 +306,8 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule)
old_rule = insert_rule(cls, subtable, rule);
if (!old_rule) {
+ int i;
+
if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX) {
ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow);
rule->partition = create_partition(cls, subtable, metadata);
@@ -280,6 +317,10 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule)
subtable->n_rules++;
cls->n_rules++;
+
+ for (i = 0; i < cls->n_tries; i++) {
+ trie_insert(&cls->tries[i], rule);
+ }
} else {
rule->partition = old_rule->partition;
}
@@ -346,9 +387,25 @@ classifier_remove(struct classifier *cls, struct cls_rule *rule)
} else {
update_subtables_after_removal(cls, subtable, rule->priority);
}
+
+ for (i = 0; i < cls->n_tries; i++) {
+ trie_remove(&cls->tries[i], rule);
+ }
+
cls->n_rules--;
}
+/* Prefix tree context. Ignored if field is NULL. Otherwise can skip all
+ * subtables which have more than 'match_len' bits in 'field'. If skipped,
+ * 'chekbits' prefix bits should un-wildcarded to quarantee no false matches
+ * will happen on the wildcarded datapath flow. */
+struct trie_ctx {
+ uint8_t idx; /* Index of the corresponding trie. */
+ uint8_t u32ofs; /* U32 offset of the field in question. */
+ uint8_t match_plen; /* Longest prefix than could possibly match. */
+ uint8_t checkbits; /* Prefix length needed to avoid false matches. */
+};
+
/* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
* Returns a null pointer if no rules in 'cls' match 'flow'. If multiple rules
* of equal priority match 'flow', returns one arbitrarily.
@@ -365,6 +422,8 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow,
struct cls_subtable *subtable;
struct cls_rule *best;
tag_type tags;
+ struct trie_ctx trie_ctx[CLS_N_TRIES];
+ int i, n_tries = 0;
/* Determine 'tags' such that, if 'subtable->tag' doesn't intersect them,
* then 'flow' cannot possibly match in 'subtable':
@@ -390,6 +449,13 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow,
hash_metadata(flow->metadata)));
tags = partition ? partition->tags : TAG_ARBITRARY;
+ /* Initialize trie contexts for match_find(). */
+ for (i = 0; i < cls->n_tries; i++) {
+ if (trie_lookup(&cls->tries[i], flow, &trie_ctx[n_tries])) {
+ trie_ctx[n_tries].idx = i;
+ n_tries++;
+ }
+ }
best = NULL;
LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) {
struct cls_rule *rule;
@@ -397,8 +463,7 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow,
if (!tag_intersects(tags, subtable->tag)) {
continue;
}
-
- rule = find_match(subtable, flow, wc);
+ rule = find_match(subtable, flow, trie_ctx, n_tries, wc);
if (rule) {
best = rule;
LIST_FOR_EACH_CONTINUE (subtable, list_node,
@@ -411,8 +476,7 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow,
if (!tag_intersects(tags, subtable->tag)) {
continue;
}
-
- rule = find_match(subtable, flow, wc);
+ rule = find_match(subtable, flow, trie_ctx, n_tries, wc);
if (rule && rule->priority > best->priority) {
best = rule;
}
@@ -420,6 +484,7 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow,
break;
}
}
+
return best;
}
@@ -711,6 +776,12 @@ insert_subtable(struct classifier *cls, const struct minimask *mask)
? 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,
+ NULL);
+ }
+
return subtable;
}
@@ -823,8 +894,54 @@ update_subtables_after_removal(struct classifier *cls,
}
}
+/* Return 'true' if can skip rest of the subtable based on the prefix trie
+ * lookup results. */
+static inline bool
+check_tries(const struct trie_ctx trie_ctx[CLS_N_TRIES], unsigned int n_tries,
+ const uint8_t field_plen[CLS_N_TRIES], uint8_t next_u32ofs,
+ struct flow_wildcards *wc)
+{
+ int j;
+ /* Check if we could avoid fully unwildcarding the next level of
+ * fields using the prefix tries. The trie checks are done only as
+ * needed to avoid folding in additional bits to the wildcards mask. */
+ for (j = 0; j < n_tries; j++) {
+ const struct trie_ctx *ctx = &trie_ctx[j];
+ /* Possible to skip the whole subtable if subtable's prefix on the
+ * field is longer than what is known to match based on the
+ * trie lookup. */
+ if (field_plen[ctx->idx] > ctx->match_plen) {
+ /* Can safely skip if no wildcarding is done... */
+ if (!wc) {
+ return true;
+ }
+ /* ...or if the field is already unwildcarded. */
+ if (mask_prefix_bits_set(wc, ctx->u32ofs, ctx->checkbits)) {
+ return true;
+ }
+ /* We want the trie lookup to never result in unwildcarding any
+ * bits that would not be unwildcarded otherwise. First check
+ * that the next lookup would cover the trie field, then check
+ * that the trie result will not unwildcard more bits than the
+ * next lookup will. */
+ if (ctx->u32ofs < next_u32ofs &&
+ !(ctx->checkbits > field_plen[ctx->idx])) {
+ /* Unwildcard the bits and skip the rest. */
+ mask_set_prefix_bits(wc, ctx->u32ofs, ctx->checkbits);
+ /* Note: Prerequisite already unwildcarded, as the only
+ * prerequisite of the supported trie lookup fields is
+ * the ethertype, which is always unwildcarded as part
+ * of an earlier lookup segment. */
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
static struct cls_rule *
find_match(const struct cls_subtable *subtable, const struct flow *flow,
+ const struct trie_ctx trie_ctx[CLS_N_TRIES], unsigned int n_tries,
struct flow_wildcards *wc)
{
uint32_t basis = 0, hash;
@@ -836,6 +953,10 @@ find_match(const struct cls_subtable *subtable, const struct flow *flow,
for (i = 0; i < subtable->n_indices; i++) {
struct hindex_node *inode;
+ if (check_tries(trie_ctx, n_tries, subtable->trie_plen,
+ subtable->index_ofs[i], wc)) {
+ goto range_out;
+ }
hash = flow_hash_in_minimask_range(flow, &subtable->mask, prev_u32ofs,
subtable->index_ofs[i],
&basis);
@@ -844,11 +965,7 @@ find_match(const struct cls_subtable *subtable, const struct flow *flow,
if (!inode) {
/* No match, can stop immediately, but must fold in the mask
* covered so far. */
- if (wc) {
- flow_wildcards_fold_minimask_range(wc, &subtable->mask, 0,
- prev_u32ofs);
- }
- return NULL;
+ goto range_out;
}
/* Check if we have narrowed down to a single rule already. This
* check shows a measurable benefit with non-trivial flow tables.
@@ -868,6 +985,10 @@ find_match(const struct cls_subtable *subtable, const struct flow *flow,
}
}
}
+ /* Trie check for the final range. */
+ if (check_tries(trie_ctx, n_tries, subtable->trie_plen, FLOW_U32S, wc)) {
+ goto range_out;
+ }
/* Have 'rule' already if there is a single non-matching rule. */
if (!rule) {
hash = flow_hash_in_minimask_range(flow, &subtable->mask, prev_u32ofs,
@@ -884,6 +1005,14 @@ find_match(const struct cls_subtable *subtable, const struct flow *flow,
flow_wildcards_fold_minimask(wc, &subtable->mask);
}
return rule;
+
+ range_out:
+ /* Must unwildcard the fields looked up so far, if any. */
+ if (wc && prev_u32ofs) {
+ flow_wildcards_fold_minimask_range(wc, &subtable->mask,
+ 0, prev_u32ofs);
+ }
+ return NULL;
}
static struct cls_rule *
@@ -978,3 +1107,443 @@ next_rule_in_list(struct cls_rule *rule)
struct cls_rule *next = next_rule_in_list__(rule);
return next->priority < rule->priority ? next : NULL;
}
+
+/* A longest-prefix match tree. */
+/* Max bits per node. Also tested with 16, 8, and 5. */
+#define TRIE_PREFIX_BITS 32
+
+struct trie_node {
+ uint32_t prefix; /* Prefix bits for this node, MSB first. */
+ uint8_t nbits; /* Never zero, except for the root node. */
+ unsigned int n_rules; /* Number of rules that have this prefix. */
+ struct trie_node *edges[2]; /* both NULL if leaf. */
+};
+
+/* Return min(TRIE_PREFIX_BITS,plen) bits of the 'prefix', starting at bit
+ * offset 'ofs'. */
+static uint32_t
+trie_get_prefix(ovs_be32 *pr, const unsigned int ofs, const unsigned int plen)
+{
+ uint32_t prefix;
+ const unsigned int keep = MIN(plen, TRIE_PREFIX_BITS);
+
+ if (!plen) {
+ return 0;
+ }
+ pr += ofs / 32; /* Where to start. */
+ prefix = ntohl(*pr) << ofs % 32;
+ if (ofs % 32 > 32 - TRIE_PREFIX_BITS && plen > 32 - ofs % 32) {
+ /* Have space and need more than we have already. */
+ prefix |= ntohl(*++pr) >> (32 - ofs % 32);
+ }
+ if (keep < 32) { /* Clear extra bits */
+ prefix &= ~0u << (32 - keep);
+ }
+ return prefix;
+}
+
+/* Return the bit at (0-based) offset 'ofs' as an int. */
+static unsigned int
+be_get_bit_at(const ovs_be32 value[], unsigned int ofs)
+{
+ return (((const uint8_t *)value)[ofs / 8] >> (7 - ofs % 8)) & 1;
+}
+
+/* Return the bit at (0-based) offset 'ofs' as an int. */
+static unsigned int
+get_bit_at(const uint32_t prefix, unsigned int ofs)
+{
+ return (prefix >> (31 - ofs)) & 1;
+}
+
+/* Create new branch. */
+static struct trie_node *
+trie_branch_create(ovs_be32 *prefix, unsigned int ofs, unsigned int plen,
+ unsigned int n_rules)
+{
+ struct trie_node *node = xmalloc(sizeof *node);
+
+ node->prefix = trie_get_prefix(prefix, ofs, plen);
+
+ if (plen <= TRIE_PREFIX_BITS) {
+ node->nbits = plen;
+ node->edges[0] = NULL;
+ node->edges[1] = NULL;
+ node->n_rules = n_rules;
+ } else { /* Need intermediate nodes. */
+ struct trie_node *subnode = trie_branch_create(prefix,
+ ofs + TRIE_PREFIX_BITS,
+ plen - TRIE_PREFIX_BITS,
+ n_rules);
+ int bit = get_bit_at(subnode->prefix, 0);
+ node->nbits = TRIE_PREFIX_BITS;
+ node->edges[bit] = subnode;
+ node->edges[!bit] = NULL;
+ node->n_rules = 0;
+ }
+ return node;
+}
+
+static void
+trie_node_destroy(struct trie_node *node)
+{
+ ovs_assert(!node->n_rules);
+ free(node);
+}
+
+static void
+trie_destroy(struct trie_node *node)
+{
+ if (node->edges[0]) {
+ trie_destroy(node->edges[0]);
+ }
+ if (node->edges[1]) {
+ trie_destroy(node->edges[1]);
+ }
+ free(node);
+}
+
+static bool
+trie_is_leaf(const struct trie_node *trie) {
+ return !trie->edges[0] && !trie->edges[1]; /* No children. */
+};
+
+/* Return the number of equal bits in 'node' prefix and a 'value' starting
+ * at bit 'ofs'. */
+static unsigned int
+trie_equal_bits(const struct trie_node *node, const ovs_be32 value[],
+ const unsigned int ofs)
+{
+ uint32_t diff = node->prefix ^ ntohl(value[ofs / 32]) << ofs % 32;
+
+ ovs_assert(node->nbits <= TRIE_PREFIX_BITS);
+
+ if (node->nbits < 32) {
+ return raw_clz(diff | ~0u >> node->nbits);
+ }
+ return clz(diff);
+}
+
+/* Return the number of equal bits in 'node' prefix and a 'prefix' starting
+ * at bit 'ofs', of length 'plen'. */
+static unsigned int
+trie_prefix_equal_bits(const struct trie_node *node, const ovs_be32 prefix[],
+ const unsigned int ofs, const unsigned int plen)
+{
+ uint32_t diff = node->prefix ^ ntohl(prefix[ofs / 32]) << ofs % 32;
+ int bits = MIN(node->nbits, plen - ofs);
+
+ ovs_assert(node->nbits <= TRIE_PREFIX_BITS);
+
+ if (bits < 32) {
+ return raw_clz(diff | ~0u >> bits);
+ }
+ return clz(diff);
+}
+
+static void
+mask_set_prefix_bits(struct flow_wildcards *wc, uint8_t u32ofs, uint8_t nbits)
+{
+ ovs_be32 *mask = &((ovs_be32 *)&wc->masks)[u32ofs];
+ unsigned int i;
+
+ for (i = 0; i < nbits / 32; i++) {
+ mask[i] = htonl(~0);
+ }
+ if (nbits % 32) {
+ mask[i] |= htonl(~0u << (32 - nbits % 32));
+ }
+}
+
+static bool
+mask_prefix_bits_set(const struct flow_wildcards *wc, uint8_t u32ofs,
+ uint8_t nbits)
+{
+ ovs_be32 *mask = &((ovs_be32 *)&wc->masks)[u32ofs];
+ unsigned int i;
+ ovs_be32 zeroes = 0;
+
+ for (i = 0; i < nbits / 32; i++) {
+ zeroes |= ~mask[i];
+ }
+ if (nbits % 32) {
+ zeroes |= ~mask[i] & htonl(~0u << (32 - nbits % 32));
+ }
+
+ return !zeroes; /* All 'nbits' bits set. */
+}
+
+/* Return the prefix mask length necessary to find the longest-prefix match for
+ * the '*value' in the prefix tree 'node'.
+ * '*checkbits' is set to the number of bits in the prefix mask necessary to
+ * determine a mismatch, in case there are longer prefixes in the tree below
+ * the one that matched. */
+static uint8_t
+trie_lookup_value(const struct trie_node *node, const ovs_be32 *value,
+ uint8_t *checkbits)
+{
+ unsigned int plen = 0, match_len = 0;
+
+ for (;;) {
+ unsigned int eqbits;
+ /* Check if this edge can be followed. */
+ eqbits = trie_equal_bits(node, value, plen);
+ plen += eqbits;
+ if (eqbits < node->nbits) { /* Mismatch, nothing more to be found. */
+ /* Bit at offset plen differed. */
+ *checkbits = plen + 1; /* Includes the one mismatching bit. */
+ break;
+ }
+ /* Full match, check if rules exist at this prefix length. */
+ if (node->n_rules > 0) {
+ match_len = plen;
+ }
+ if (trie_is_leaf(node)) {
+ *checkbits = plen;
+ break;
+ }
+ node = node->edges[be_get_bit_at(value, plen)];
+ if (!node) {
+ /* Dead end, but the other branch exists (since !leaf) */
+ *checkbits = plen + 1;
+ break;
+ }
+ }
+ return match_len;
+}
+
+/* Returns true if the '*trie_ctx' is valid on return. */
+static bool
+trie_lookup(const struct cls_trie *trie, const struct flow *flow,
+ struct trie_ctx *trie_ctx)
+{
+ const struct mf_field *mf = trie->field;
+
+ if (!trie->root || !mf || !mf_are_prereqs_ok(mf, flow)) {
+ /* Can not skip based on this field, or the current flow
+ * does not match the prerequisites for the field. Some match
+ * fields are used for multiple purposes, so we should try to
+ * skip only when prerequisities are met. */
+ return false;
+ }
+
+ trie_ctx->u32ofs = mf->flow_u32ofs;
+ trie_ctx->match_plen =
+ trie_lookup_value(trie->root, &((ovs_be32 *)flow)[mf->flow_u32ofs],
+ &trie_ctx->checkbits);
+ return true;
+}
+
+/* Returns the length of a longest-prefix match mask for the field 'mf' in
+ * 'match'. When the returned length is non-zero, returns the u32 offset to
+ * the miniflow data in '*miniflow_index', if 'miniflow_index' is not NULL.
+ */
+static uint8_t
+minimask_get_prefix_len(const struct minimask *minimask,
+ const struct mf_field *mf,
+ unsigned int *miniflow_index)
+{
+ const struct miniflow *mflow = &minimask->masks;
+ unsigned int u32_ofs, u32_end;
+ unsigned int ofs32;
+ uint8_t nbits = 0, mask_tz = 0; /* Non-zero when end of mask seen. */
+
+ if (!mf || mf->n_bytes % 4) {
+ return 0;
+ }
+
+ u32_ofs = mf->flow_u32ofs;
+
+ /* Scan to the starting offset of the mask data. */
+ ofs32 = popcount64(mflow->map & ((UINT64_C(1) << u32_ofs) - 1));
+
+ if (miniflow_index) {
+ *miniflow_index = ofs32; /* Starting miniflow data offset. */
+ }
+
+ u32_end = u32_ofs + mf->n_bytes / 4;
+
+ for (; u32_ofs < u32_end; ++u32_ofs) {
+ uint32_t mask = mflow->map & (UINT64_C(1) << u32_ofs)
+ ? ntohl((OVS_FORCE ovs_be32)mflow->values[ofs32++]) : 0;
+
+ /* Validate mask, count the mask length. */
+ if (mask_tz) {
+ if (mask) {
+ return 0; /* No bits allowed after mask ended. */
+ }
+ } else {
+ if (mask) {
+ mask_tz = raw_ctz(mask);
+ if (~mask & (~0u << mask_tz)) {
+ return 0; /* Mask not contiguous. */
+ }
+ nbits += 32 - mask_tz;
+ } else {
+ mask_tz = 32; /* End of mask seen. */
+ }
+ }
+ }
+ return nbits;
+}
+
+/* Insert rule in to the prefix tree. */
+static void
+trie_insert(struct cls_trie *trie, const struct cls_rule *rule)
+{
+ struct trie_node *node;
+ const struct mf_field *mf = trie->field;
+ int ofs, mlen;
+ ovs_be32 *prefix;
+ struct trie_node **edge;
+ unsigned int miniflow_index;
+
+ if (!mf) {
+ return;
+ }
+
+ ovs_assert(mf->flow_u32ofs >= 0 && mf->n_bits % 32 == 0);
+
+ /* Get mask length and location in the miniflow.
+ * Note: flow and mask have data at same offsets!
+ */
+ mlen = minimask_get_prefix_len(&rule->match.mask, mf, &miniflow_index);
+ if (!mlen) {
+ return; /* Rule's mask not compatible or zero length. */
+ }
+ prefix = (OVS_FORCE ovs_be32 *)&rule->match.flow.values[miniflow_index];
+
+ if (!trie->root) {
+ /* Insert as the lone rule in the tree. */
+ trie->root = trie_branch_create(prefix, 0, mlen, 1);
+ return;
+ }
+ /* Walk the tree. */
+ edge = &trie->root; /* Edge most recently followed. */
+ node = *edge;
+ ofs = 0;
+ while (node) {
+ unsigned int eqbits = trie_prefix_equal_bits(node, prefix, ofs, mlen);
+
+ /* Only the root may have no prefix */
+ ovs_assert(edge == &trie->root || node->nbits);
+
+ ofs += eqbits;
+
+ if (eqbits < node->nbits) {
+ /* Mismatch, new node needs to be inserted above. */
+ int old_branch = get_bit_at(node->prefix, eqbits);
+
+ /* New parent node. */
+ *edge = trie_branch_create(prefix, ofs - eqbits, eqbits,
+ ofs == mlen ? 1 : 0);
+
+ /* Adjust old node for it's new position in the tree. */
+ node->prefix <<= eqbits;
+ node->nbits -= eqbits;
+ (*edge)->edges[old_branch] = node;
+
+ /* Check if need a new branch for the new rule. */
+ if (ofs < mlen) {
+ (*edge)->edges[!old_branch]
+ = trie_branch_create(prefix, ofs, mlen - ofs, 1);
+ }
+ return;
+ }
+
+ /* Full match so far. */
+
+ if (ofs == mlen) {
+ /* Full match at the current node, rule needs to be added here. */
+ node->n_rules++;
+ return;
+ }
+ /* Go deeper. */
+ edge = &node->edges[be_get_bit_at(prefix, ofs)];
+ if (!*edge) {
+ /* Must insert a new tree branch for the new rule. */
+ *edge = trie_branch_create(prefix, ofs, mlen - ofs, 1);
+ return;
+ }
+ node = *edge;
+
+ ovs_assert(ofs < mlen);
+ }
+}
+
+static void
+trie_remove(struct cls_trie *trie, const struct cls_rule *rule)
+{
+ struct trie_node *node;
+ const struct mf_field *mf = trie->field;
+ int ofs, mlen;
+ ovs_be32 *prefix;
+ struct trie_node **edge;
+ unsigned int miniflow_index;
+
+ if (!mf || !trie->root) {
+ return; /* Nothing to be done. */
+ }
+
+ ovs_assert(mf->flow_u32ofs >= 0 && mf->n_bits % 32 == 0);
+
+ /* Get mask length and location in the miniflow. */
+ mlen = minimask_get_prefix_len(&rule->match.mask, mf, &miniflow_index);
+ if (!mlen) {
+ return; /* Rule's mask not compatible or zero length. */
+ }
+ prefix = (OVS_FORCE ovs_be32 *)&rule->match.flow.values[miniflow_index];
+
+ /* Walk the tree. */
+ edge = &trie->root; /* Edge most recently followed. */
+ node = *edge;
+ ofs = 0;
+ while (node) {
+ unsigned int eqbits = trie_prefix_equal_bits(node, prefix, ofs, mlen);
+
+ if (eqbits < node->nbits) {
+ /* Mismatch, nothing to be removed. This should never happen, as
+ * only rules in the classifier are ever removed. */
+ ovs_assert(eqbits == node->nbits);
+ return;
+ }
+
+ /* Full match so far. */
+ ofs += eqbits;
+
+ if (ofs == mlen) {
+ /* Full match at the current node, rule needs to be added here. */
+ if (node->n_rules) {
+ node->n_rules--;
+ }
+ if (!node->n_rules && /* Remove this node from the tree? */
+ !(node->edges[0] && node->edges[1])) {
+ /* No rules and at most one child node, remove this node. */
+ struct trie_node *next;
+ next = node->edges[0] ? node->edges[0] : node->edges[1];
+
+ if (next) {
+ if (node->nbits + next->nbits > TRIE_PREFIX_BITS) {
+ return; /* Cannot combine. */
+ }
+ /* Combine node with next. */
+ next->prefix = node->prefix | next->prefix >> node->nbits;
+ next->nbits += node->nbits;
+ }
+ *edge = next;
+ trie_node_destroy(node);
+ }
+ return;
+ }
+ /* Go deeper. */
+ edge = &node->edges[be_get_bit_at(prefix, ofs)];
+ if (!*edge) {
+ /* Cannot go deeper. This should never happen, since only rules
+ * that actually exist in the classifier are ever removed. */
+ ovs_assert(*edge);
+ return;
+ }
+ node = *edge;
+ ovs_assert(ofs < mlen);
+ }
+}
diff --git a/lib/classifier.h b/lib/classifier.h
index 97c9b3b..9c50b32 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -106,6 +106,7 @@
#include "hmap.h"
#include "list.h"
#include "match.h"
+#include "meta-flow.h"
#include "tag.h"
#include "openflow/nicira-ext.h"
#include "openflow/openflow.h"
@@ -118,6 +119,15 @@ extern "C" {
/* Needed only for the lock annotation in struct classifier. */
extern struct ovs_mutex ofproto_mutex;
+struct trie_node;
+
+/* Maximum number of prefix trees per classifier. */
+#define CLS_N_TRIES 3
+
+struct cls_trie {
+ const struct mf_field *field; /* Trie field, or NULL. */
+ struct trie_node *root; /* NULL if none. */
+};
enum { CLS_MAX_INDICES = 3 };
@@ -132,6 +142,8 @@ struct classifier {
*/
struct hmap partitions; /* Contains "struct cls_partition"s. */
struct ovs_rwlock rwlock OVS_ACQ_AFTER(ofproto_mutex);
+ struct cls_trie tries[CLS_N_TRIES];
+ unsigned int n_tries;
};
/* A set of rules that all have the same fields wildcarded. */
@@ -149,6 +161,7 @@ struct cls_subtable {
uint8_t n_indices; /* How many indices to use. */
uint8_t index_ofs[CLS_MAX_INDICES]; /* u32 flow segment boundaries. */
struct hindex indices[CLS_MAX_INDICES]; /* Search indices. */
+ uint8_t trie_plen[CLS_N_TRIES]; /* Trie prefix length of the 'mask' */
};
/* Returns true if 'table' is a "catch-all" subtable that will match every
diff --git a/lib/flow.c b/lib/flow.c
index 6db7aa6..5833de5 100644
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -1150,12 +1150,16 @@ miniflow_alloc_values(struct miniflow *flow, int n)
/* Completes an initialization of 'dst' as a miniflow copy of 'src' begun by
* the caller. The caller must have already initialized 'dst->map' properly
- * to indicate the nonzero uint32_t elements of 'src'. 'n' must be the number
- * of 1-bits in 'dst->map'.
+ * to indicate the significant uint32_t elements of 'src'. 'n' must be the
+ * number of 1-bits in 'dst->map'.
+ *
+ * Normally the significant elements are the ones that are non-zero. However,
+ * when a miniflow is initialized from a (mini)mask, the values can be zeroes,
+ * so that the flow and mask always have the same maps.
*
* This function initializes 'dst->values' (either inline if possible or with
- * malloc() otherwise) and copies the nonzero uint32_t elements of 'src' into
- * it. */
+ * malloc() otherwise) and copies the uint32_t elements of 'src' indicated by
+ * 'dst->map' into it. */
static void
miniflow_init__(struct miniflow *dst, const struct flow *src, int n)
{
diff --git a/lib/meta-flow.c b/lib/meta-flow.c
index 9f39c18..fd27c41 100644
--- a/lib/meta-flow.c
+++ b/lib/meta-flow.c
@@ -37,6 +37,9 @@
VLOG_DEFINE_THIS_MODULE(meta_flow);
+#define FLOW_U32OFS(FIELD) \
+ offsetof(struct flow, FIELD) % 4 ? -1 : offsetof(struct flow, FIELD) / 4
+
#define MF_FIELD_SIZES(MEMBER) \
sizeof ((union mf_value *)0)->MEMBER, \
8 * sizeof ((union mf_value *)0)->MEMBER
@@ -59,6 +62,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_TUNNEL_ID, "OXM_OF_TUNNEL_ID",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ FLOW_U32OFS(tunnel.tun_id),
}, {
MFF_TUN_SRC, "tun_src", NULL,
MF_FIELD_SIZES(be32),
@@ -70,6 +74,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
NXM_NX_TUN_IPV4_SRC, "NXM_NX_TUN_IPV4_SRC",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ FLOW_U32OFS(tunnel.ip_src),
}, {
MFF_TUN_DST, "tun_dst", NULL,
MF_FIELD_SIZES(be32),
@@ -81,6 +86,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
NXM_NX_TUN_IPV4_DST, "NXM_NX_TUN_IPV4_DST",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ FLOW_U32OFS(tunnel.ip_dst),
}, {
MFF_TUN_FLAGS, "tun_flags", NULL,
MF_FIELD_SIZES(be16),
@@ -92,6 +98,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
0, NULL,
OFPUTIL_P_NONE,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_TUN_TTL, "tun_ttl", NULL,
MF_FIELD_SIZES(u8),
@@ -103,6 +110,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
0, NULL,
OFPUTIL_P_NONE,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_TUN_TOS, "tun_tos", NULL,
MF_FIELD_SIZES(u8),
@@ -114,6 +122,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
0, NULL,
OFPUTIL_P_NONE,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_METADATA, "metadata", NULL,
MF_FIELD_SIZES(be64),
@@ -125,6 +134,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_METADATA, "OXM_OF_METADATA",
OFPUTIL_P_NXM_OF11_UP,
OFPUTIL_P_NXM_OF11_UP,
+ FLOW_U32OFS(metadata),
}, {
MFF_IN_PORT, "in_port", NULL,
MF_FIELD_SIZES(be16),
@@ -136,6 +146,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
NXM_OF_IN_PORT, "NXM_OF_IN_PORT",
OFPUTIL_P_ANY, /* OF11+ via mapping to 32 bits. */
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_IN_PORT_OXM, "in_port_oxm", NULL,
MF_FIELD_SIZES(be32),
@@ -147,6 +158,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IN_PORT, "OXM_OF_IN_PORT",
OFPUTIL_P_OF11_UP,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_SKB_PRIORITY, "skb_priority", NULL,
MF_FIELD_SIZES(be32),
@@ -158,6 +170,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
0, NULL,
OFPUTIL_P_NONE,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_PKT_MARK, "pkt_mark", NULL,
MF_FIELD_SIZES(be32),
@@ -169,6 +182,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
NXM_NX_PKT_MARK, "NXM_NX_PKT_MARK",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
},
#define REGISTER(IDX) \
@@ -183,6 +197,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
NXM_NX_REG(IDX), "NXM_NX_REG" #IDX, \
OFPUTIL_P_NXM_OXM_ANY, \
OFPUTIL_P_NXM_OXM_ANY, \
+ FLOW_U32OFS(regs[IDX]), \
}
#if FLOW_N_REGS > 0
REGISTER(0),
@@ -227,6 +242,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ETH_SRC, "OXM_OF_ETH_SRC",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OF11_UP, /* Bitwise masking only with NXM and OF11+! */
+ -1,
}, {
MFF_ETH_DST, "eth_dst", "dl_dst",
MF_FIELD_SIZES(mac),
@@ -238,6 +254,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ETH_DST, "OXM_OF_ETH_DST",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OF11_UP, /* Bitwise masking only with NXM and OF11+! */
+ -1,
}, {
MFF_ETH_TYPE, "eth_type", "dl_type",
MF_FIELD_SIZES(be16),
@@ -249,6 +266,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ETH_TYPE, "OXM_OF_ETH_TYPE",
OFPUTIL_P_ANY,
OFPUTIL_P_NONE,
+ -1,
},
{
@@ -262,6 +280,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
NXM_OF_VLAN_TCI, "NXM_OF_VLAN_TCI",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
}, {
MFF_DL_VLAN, "dl_vlan", NULL,
sizeof(ovs_be16), 12,
@@ -273,6 +292,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
0, NULL,
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
}, {
MFF_VLAN_VID, "vlan_vid", NULL,
sizeof(ovs_be16), 12,
@@ -284,6 +304,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_VLAN_VID, "OXM_OF_VLAN_VID",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
}, {
MFF_DL_VLAN_PCP, "dl_vlan_pcp", NULL,
1, 3,
@@ -295,6 +316,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
0, NULL,
OFPUTIL_P_ANY, /* Will be mapped to NXM and OXM. */
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_VLAN_PCP, "vlan_pcp", NULL,
1, 3,
@@ -306,6 +328,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_VLAN_PCP, "OXM_OF_VLAN_PCP",
OFPUTIL_P_ANY, /* Will be mapped to OF10 and NXM. */
OFPUTIL_P_NONE,
+ -1,
},
/* ## ---- ## */
@@ -322,6 +345,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_MPLS_LABEL, "OXM_OF_MPLS_LABEL",
OFPUTIL_P_NXM_OF11_UP,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_MPLS_TC, "mpls_tc", NULL,
1, 3,
@@ -333,6 +357,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_MPLS_TC, "OXM_OF_MPLS_TC",
OFPUTIL_P_NXM_OF11_UP,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_MPLS_BOS, "mpls_bos", NULL,
1, 1,
@@ -344,6 +369,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_MPLS_BOS, "OXM_OF_MPLS_BOS",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NONE,
+ -1,
},
/* ## -- ## */
@@ -361,6 +387,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IPV4_SRC, "OXM_OF_IPV4_SRC",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OF11_UP,
+ FLOW_U32OFS(nw_src),
}, {
MFF_IPV4_DST, "ip_dst", "nw_dst",
MF_FIELD_SIZES(be32),
@@ -372,6 +399,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IPV4_DST, "OXM_OF_IPV4_DST",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OF11_UP,
+ FLOW_U32OFS(nw_dst),
},
{
@@ -385,6 +413,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IPV6_SRC, "OXM_OF_IPV6_SRC",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ FLOW_U32OFS(ipv6_src),
}, {
MFF_IPV6_DST, "ipv6_dst", NULL,
MF_FIELD_SIZES(ipv6),
@@ -396,6 +425,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IPV6_DST, "OXM_OF_IPV6_DST",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ FLOW_U32OFS(ipv6_dst),
},
{
MFF_IPV6_LABEL, "ipv6_label", NULL,
@@ -408,6 +438,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IPV6_FLABEL, "OXM_OF_IPV6_FLABEL",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
},
{
@@ -421,6 +452,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IP_PROTO, "OXM_OF_IP_PROTO",
OFPUTIL_P_ANY,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_IP_DSCP, "nw_tos", NULL,
MF_FIELD_SIZES(u8),
@@ -432,6 +464,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
NXM_OF_IP_TOS, "NXM_OF_IP_TOS",
OFPUTIL_P_ANY, /* Will be shifted for OXM. */
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_IP_DSCP_SHIFTED, "ip_dscp", NULL,
1, 6,
@@ -443,6 +476,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IP_DSCP, "OXM_OF_IP_DSCP",
OFPUTIL_P_ANY, /* Will be shifted for non-OXM. */
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_IP_ECN, "nw_ecn", "ip_ecn",
1, 2,
@@ -454,6 +488,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IP_ECN, "OXM_OF_IP_ECN",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_IP_TTL, "nw_ttl", NULL,
MF_FIELD_SIZES(u8),
@@ -465,6 +500,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
NXM_NX_IP_TTL, "NXM_NX_IP_TTL",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_IP_FRAG, "ip_frag", NULL,
1, 2,
@@ -476,6 +512,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
NXM_NX_IP_FRAG, "NXM_NX_IP_FRAG",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
},
{
@@ -489,6 +526,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ARP_OP, "OXM_OF_ARP_OP",
OFPUTIL_P_ANY,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_ARP_SPA, "arp_spa", NULL,
MF_FIELD_SIZES(be32),
@@ -500,6 +538,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ARP_SPA, "OXM_OF_ARP_SPA",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OF11_UP,
+ -1,
}, {
MFF_ARP_TPA, "arp_tpa", NULL,
MF_FIELD_SIZES(be32),
@@ -511,6 +550,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ARP_TPA, "OXM_OF_ARP_TPA",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OF11_UP,
+ -1,
}, {
MFF_ARP_SHA, "arp_sha", NULL,
MF_FIELD_SIZES(mac),
@@ -522,6 +562,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ARP_SHA, "OXM_OF_ARP_SHA",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
}, {
MFF_ARP_THA, "arp_tha", NULL,
MF_FIELD_SIZES(mac),
@@ -533,6 +574,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ARP_THA, "OXM_OF_ARP_THA",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
},
/* ## -- ## */
@@ -550,6 +592,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_TCP_SRC, "OXM_OF_TCP_SRC",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
}, {
MFF_TCP_DST, "tcp_dst", "tp_dst",
MF_FIELD_SIZES(be16),
@@ -561,6 +604,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_TCP_DST, "OXM_OF_TCP_DST",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
}, {
MFF_TCP_FLAGS, "tcp_flags", NULL,
2, 12,
@@ -572,6 +616,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
NXM_NX_TCP_FLAGS, "NXM_NX_TCP_FLAGS",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
},
{
@@ -585,6 +630,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_UDP_SRC, "OXM_OF_UDP_SRC",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
}, {
MFF_UDP_DST, "udp_dst", NULL,
MF_FIELD_SIZES(be16),
@@ -596,6 +642,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_UDP_DST, "OXM_OF_UDP_DST",
OFPUTIL_P_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
},
{
@@ -609,6 +656,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_SCTP_SRC, "OXM_OF_SCTP_SRC",
OFPUTIL_P_NXM_OF11_UP,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
}, {
MFF_SCTP_DST, "sctp_dst", NULL,
MF_FIELD_SIZES(be16),
@@ -620,6 +668,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_SCTP_DST, "OXM_OF_SCTP_DST",
OFPUTIL_P_NXM_OF11_UP,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
},
{
@@ -633,6 +682,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ICMPV4_TYPE, "OXM_OF_ICMPV4_TYPE",
OFPUTIL_P_ANY,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_ICMPV4_CODE, "icmp_code", NULL,
MF_FIELD_SIZES(u8),
@@ -644,6 +694,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ICMPV4_CODE, "OXM_OF_ICMPV4_CODE",
OFPUTIL_P_ANY,
OFPUTIL_P_NONE,
+ -1,
},
{
@@ -657,6 +708,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ICMPV6_TYPE, "OXM_OF_ICMPV6_TYPE",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NONE,
+ -1,
}, {
MFF_ICMPV6_CODE, "icmpv6_code", NULL,
MF_FIELD_SIZES(u8),
@@ -668,6 +720,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ICMPV6_CODE, "OXM_OF_ICMPV6_CODE",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NONE,
+ -1,
},
/* ## ---- ## */
@@ -685,6 +738,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IPV6_ND_TARGET, "OXM_OF_IPV6_ND_TARGET",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
}, {
MFF_ND_SLL, "nd_sll", NULL,
MF_FIELD_SIZES(mac),
@@ -696,6 +750,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IPV6_ND_SLL, "OXM_OF_IPV6_ND_SLL",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
}, {
MFF_ND_TLL, "nd_tll", NULL,
MF_FIELD_SIZES(mac),
@@ -707,6 +762,7 @@ const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_IPV6_ND_TLL, "OXM_OF_IPV6_ND_TLL",
OFPUTIL_P_NXM_OXM_ANY,
OFPUTIL_P_NXM_OXM_ANY,
+ -1,
}
};
diff --git a/lib/meta-flow.h b/lib/meta-flow.h
index c2b0bbc..fdcfcd3 100644
--- a/lib/meta-flow.h
+++ b/lib/meta-flow.h
@@ -296,6 +296,10 @@ struct mf_field {
enum ofputil_protocol usable_protocols; /* If fully/cidr masked. */
/* If partially/non-cidr masked. */
enum ofputil_protocol usable_protocols_bitwise;
+
+ int flow_u32ofs; /* Field's U32 offset in "struct flow", if
+ * longest-prefix match is supported for the
+ * field, or -1. */
};
/* The representation of a field's value. */
diff --git a/lib/ofp-util.h b/lib/ofp-util.h
index fef85e0..36d8801 100644
--- a/lib/ofp-util.h
+++ b/lib/ofp-util.h
@@ -20,9 +20,9 @@
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
-#include "classifier.h"
#include "compiler.h"
#include "flow.h"
+#include "list.h"
#include "match.h"
#include "netdev.h"
#include "openflow/nicira-ext.h"
diff --git a/tests/classifier.at b/tests/classifier.at
index 546c8f7..0b38b2f 100644
--- a/tests/classifier.at
+++ b/tests/classifier.at
@@ -45,7 +45,7 @@ Datapath actions: 1
])
AT_CHECK([ovs-appctl ofproto/trace br0 'in_port=1,dl_src=50:54:00:00:00:05,dl_dst=50:54:00:00:00:07,dl_type=0x0800,nw_src=192.168.0.1,nw_dst=192.168.0.2,nw_proto=6,nw_tos=0,nw_ttl=128,tp_src=8,tp_dst=80'], [0], [stdout])
AT_CHECK([tail -2 stdout], [0],
- [Relevant fields: skb_priority=0,tcp,in_port=1,nw_dst=192.168.0.2,nw_frag=no
+ [Relevant fields: skb_priority=0,tcp,in_port=1,nw_dst=192.168.0.0/16,nw_frag=no
Datapath actions: drop
])
AT_CHECK([ovs-appctl ofproto/trace br0 'in_port=1,dl_src=50:54:00:00:00:05,dl_dst=50:54:00:00:00:07,dl_type=0x0800,nw_src=192.168.0.1,nw_dst=10.1.2.15,nw_proto=6,nw_tos=0,nw_ttl=128,tp_src=8,tp_dst=80'], [0], [stdout])
diff --git a/tests/ofproto-dpif.at b/tests/ofproto-dpif.at
index 9a7c8ff..0c367b3 100644
--- a/tests/ofproto-dpif.at
+++ b/tests/ofproto-dpif.at
@@ -2586,7 +2586,7 @@ AT_CHECK([ovs-ofctl add-flows br0 flows.txt])
AT_CHECK([ovs-appctl netdev-dummy/receive p1 'in_port(1),eth(src=50:54:00:00:00:09,dst=50:54:00:00:00:0a),eth_type(0x0800),ipv4(src=10.0.0.2,dst=10.0.0.1,proto=1,tos=0,ttl=64,frag=no),icmp(type=8,code=0)'])
AT_CHECK([ovs-appctl netdev-dummy/receive p1 'in_port(1),eth(src=50:54:00:00:00:0b,dst=50:54:00:00:00:0c),eth_type(0x0800),ipv4(src=10.0.0.4,dst=10.0.0.3,proto=1,tos=0,ttl=64,frag=no),icmp(type=8,code=0)'])
AT_CHECK([ovs-appctl dpif/dump-flows br0 | STRIP_XOUT], [0], [dnl
-skb_priority(0),in_port(1),eth_type(0x0800),ipv4(src=10.0.0.2/255.255.255.255,dst=10.0.0.1/0.0.0.0,proto=1/0xff,tos=0/0,ttl=64/0,frag=no/0xff), packets:0, bytes:0, used:0.0s, actions: <del>
+skb_priority(0),in_port(1),eth_type(0x0800),ipv4(src=10.0.0.2/255.255.255.252,dst=10.0.0.1/0.0.0.0,proto=1/0,tos=0/0,ttl=64/0,frag=no/0xff), packets:0, bytes:0, used:0.0s, actions: <del>
skb_priority(0),in_port(1),eth_type(0x0800),ipv4(src=10.0.0.4/255.255.255.255,dst=10.0.0.3/0.0.0.0,proto=1/0xff,tos=0/0,ttl=64/0,frag=no/0xff), packets:0, bytes:0, used:0.0s, actions: <del>
])
OVS_VSWITCHD_STOP
@@ -2927,7 +2927,7 @@ AT_CHECK([ovs-ofctl add-flows br0 flows.txt])
AT_CHECK([ovs-appctl netdev-dummy/receive p1 'in_port(1),eth(src=50:54:00:00:00:09,dst=50:54:00:00:00:0a),eth_type(0x0800),ipv4(src=10.0.0.2,dst=10.0.0.1,proto=1,tos=0,ttl=64,frag=no),icmp(type=8,code=0)'])
AT_CHECK([ovs-appctl netdev-dummy/receive p1 'in_port(1),eth(src=50:54:00:00:00:0b,dst=50:54:00:00:00:0c),eth_type(0x0800),ipv4(src=10.0.0.4,dst=10.0.0.3,proto=1,tos=0,ttl=64,frag=no),icmp(type=8,code=0)'])
AT_CHECK([ovs-appctl dpif/dump-flows br0 | STRIP_XOUT], [0], [dnl
-skb_priority(0),in_port(1),eth_type(0x0800),ipv4(src=10.0.0.2/255.255.255.255,dst=10.0.0.1/0.0.0.0,proto=1/0xff,tos=0/0,ttl=64/0,frag=no/0xff), packets:0, bytes:0, used:0.0s, actions: <del>
+skb_priority(0),in_port(1),eth_type(0x0800),ipv4(src=10.0.0.2/255.255.255.252,dst=10.0.0.1/0.0.0.0,proto=1/0,tos=0/0,ttl=64/0,frag=no/0xff), packets:0, bytes:0, used:0.0s, actions: <del>
skb_priority(0),in_port(1),eth_type(0x0800),ipv4(src=10.0.0.4,dst=10.0.0.3,proto=1,tos=0,ttl=64,frag=no), packets:0, bytes:0, used:0.0s, actions: <del>
])
OVS_VSWITCHD_STOP
--
1.7.10.4
More information about the dev
mailing list