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 megaflows in
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.
This implementation creates tries for IPv4 source and
destiantion addresses in any classifier tables those
fields are used. 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.
It should be noted that this implementation does not
require any constraining of rule priorities, meaning
that this is not limited to longest-prefix match policy.
To mitigate overheads controllers could concentrate IP
address matching into specific tables.
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 <jrajaha...@nicira.com>
---
lib/classifier.c | 593 ++++++++++++++++++++++++++++++++++++++++++++++++-
lib/classifier.h | 13 ++
lib/flow.c | 12 +-
lib/meta-flow.c | 56 +++++
lib/meta-flow.h | 4 +
lib/ofp-util.h | 2 +-
lib/util.h | 13 ++
tests/classifier.at | 2 +-
tests/ofproto-dpif.at | 4 +-
9 files changed, 682 insertions(+), 17 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index 790bf8d..0c668c4 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);
@@ -169,6 +191,12 @@ classifier_init(struct classifier *cls, const uint8_t
*flow_segments)
cls->flow_segments[1] == FLOW_SEGMENT_2_ENDS_AT / 4 &&
cls->flow_segments[2] == FLOW_SEGMENT_3_ENDS_AT / 4);
}
+ 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
@@ -179,6 +207,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) {
@@ -275,6 +310,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);
@@ -284,6 +321,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;
}
@@ -350,9 +391,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.
@@ -369,6 +426,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':
@@ -394,6 +453,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;
@@ -401,8 +467,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,
@@ -415,8 +480,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;
}
@@ -424,6 +488,7 @@ classifier_lookup(const struct classifier *cls, const
struct flow *flow,
break;
}
}
+
return best;
}
@@ -715,6 +780,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;
}
@@ -827,8 +898,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;
@@ -840,6 +957,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);
@@ -848,11 +969,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. */
@@ -870,6 +987,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,
@@ -886,6 +1007,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 *
@@ -985,3 +1114,449 @@ 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_offset', if 'miniflow_offset' 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 p;
+ 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. */
+ BUILD_ASSERT(MINI_N_MAPS == 2);
+ if (u32_ofs < 32) {
+ p = popcount(mflow->map[0] & ((1u << u32_ofs) - 1));
+ } else {
+ p = popcount(mflow->map[0]);
+ p += popcount(mflow->map[1] & ((1u << (u32_ofs - 32)) - 1));
+ }
+
+ if (miniflow_index) {
+ *miniflow_index = p; /* Starting miniflow data offset. */
+ }
+
+ u32_end = u32_ofs + mf->n_bytes / 4;
+
+ for (; u32_ofs < u32_end; ++u32_ofs) {
+ uint32_t mask = (mflow->map[u32_ofs / 32] & (1u << (u32_ofs % 32)))
+ ? ntohl((OVS_FORCE ovs_be32)mflow->values[p++]) : 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 f2a2074..65fde43 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -108,6 +108,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"
@@ -120,6 +121,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 };
@@ -134,6 +144,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. */
@@ -151,6 +163,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 cef2dfc..1005b13 100644
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -1187,12 +1187,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 c0925e8..bdb2edb 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
@@ -57,6 +60,7 @@ static 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),
@@ -68,6 +72,7 @@ static 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),
@@ -79,6 +84,7 @@ static 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),
@@ -90,6 +96,7 @@ static 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),
@@ -101,6 +108,7 @@ static 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),
@@ -112,6 +120,7 @@ static 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),
@@ -123,6 +132,7 @@ static 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),
@@ -134,6 +144,7 @@ static 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),
@@ -145,6 +156,7 @@ static 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),
@@ -156,6 +168,7 @@ static 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),
@@ -167,6 +180,7 @@ static 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) \
@@ -181,6 +195,7 @@ static 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),
@@ -225,6 +240,7 @@ static 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),
@@ -236,6 +252,7 @@ static 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),
@@ -247,6 +264,7 @@ static const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ETH_TYPE, "OXM_OF_ETH_TYPE",
OFPUTIL_P_ANY,
OFPUTIL_P_NONE,
+ -1,
},
{
@@ -260,6 +278,7 @@ static 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,
@@ -271,6 +290,7 @@ static 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,
@@ -282,6 +302,7 @@ static 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,
@@ -293,6 +314,7 @@ static 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,
@@ -304,6 +326,7 @@ static 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,
},
/* ## ---- ## */
@@ -320,6 +343,7 @@ static 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,
@@ -331,6 +355,7 @@ static 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,
@@ -342,6 +367,7 @@ static 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,
},
/* ## -- ## */
@@ -359,6 +385,7 @@ static 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),
@@ -370,6 +397,7 @@ static 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),
},
{
@@ -383,6 +411,7 @@ static 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),
@@ -394,6 +423,7 @@ static 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,
@@ -406,6 +436,7 @@ static 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,
},
{
@@ -419,6 +450,7 @@ static 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),
@@ -430,6 +462,7 @@ static 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, "nw_tos_shifted", NULL,
MF_FIELD_SIZES(u8),
@@ -441,6 +474,7 @@ static 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", NULL,
1, 2,
@@ -452,6 +486,7 @@ static 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),
@@ -463,6 +498,7 @@ static 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,
@@ -474,6 +510,7 @@ static 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,
},
{
@@ -487,6 +524,7 @@ static 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),
@@ -498,6 +536,7 @@ static 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),
@@ -509,6 +548,7 @@ static 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),
@@ -520,6 +560,7 @@ static 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),
@@ -531,6 +572,7 @@ static 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,
},
/* ## -- ## */
@@ -548,6 +590,7 @@ static 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),
@@ -559,6 +602,7 @@ static 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,
@@ -570,6 +614,7 @@ static 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,
},
{
@@ -583,6 +628,7 @@ static 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),
@@ -594,6 +640,7 @@ static 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,
},
{
@@ -607,6 +654,7 @@ static 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),
@@ -618,6 +666,7 @@ static 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,
},
{
@@ -631,6 +680,7 @@ static 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),
@@ -642,6 +692,7 @@ static const struct mf_field mf_fields[MFF_N_IDS] = {
OXM_OF_ICMPV4_CODE, "OXM_OF_ICMPV4_CODE",
OFPUTIL_P_ANY,
OFPUTIL_P_NONE,
+ -1,
},
{
@@ -655,6 +706,7 @@ static 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),
@@ -666,6 +718,7 @@ static 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,
},
/* ## ---- ## */
@@ -683,6 +736,7 @@ static 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),
@@ -694,6 +748,7 @@ static 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),
@@ -705,6 +760,7 @@ static 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 11502f0..4512bdd 100644
--- a/lib/meta-flow.h
+++ b/lib/meta-flow.h
@@ -295,6 +295,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 c37ab2b..a6ef182 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/lib/util.h b/lib/util.h
index a899065..8728d8a 100644
--- a/lib/util.h
+++ b/lib/util.h
@@ -294,9 +294,15 @@ raw_ctz(uint32_t n)
{
return __builtin_ctz(n);
}
+static inline int
+raw_clz(uint32_t n)
+{
+ return __builtin_clz(n);
+}
#else
/* Defined in util.c. */
int raw_ctz(uint32_t n);
+int raw_clz(uint32_t n);
#endif
/* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */
@@ -306,6 +312,13 @@ ctz(uint32_t n)
return n ? raw_ctz(n) : 32;
}
+/* Returns the number of leading 0-bits in 'n', or 32 if 'n' is 0. */
+static inline int
+clz(uint32_t n)
+{
+ return n ? raw_clz(n) : 32;
+}
+
int log_2_floor(uint32_t);
int log_2_ceil(uint32_t);
unsigned int popcount(uint32_t);
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 9e0ea4b..73aa90d 100644
--- a/tests/ofproto-dpif.at
+++ b/tests/ofproto-dpif.at
@@ -2463,8 +2463,8 @@ 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-megaflows br0 | STRIP_XOUT], [0], [dnl
-skb_priority=0,icmp,in_port=1,nw_src=10.0.0.2,nw_frag=no, n_subfacets:1,
used:0.0s, Datapath actions: <del>
skb_priority=0,icmp,in_port=1,nw_src=10.0.0.4,nw_frag=no, n_subfacets:1,
used:0.0s, Datapath actions: <del>
+skb_priority=0,ip,in_port=1,nw_src=10.0.0.0/30,nw_frag=no, n_subfacets:1,
used:0.0s, Datapath actions: <del>
])
OVS_VSWITCHD_STOP
AT_CLEANUP
@@ -2804,8 +2804,8 @@ 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-megaflows br0 | STRIP_XOUT], [0], [dnl
-skb_priority=0,icmp,in_port=1,nw_src=10.0.0.2,nw_frag=no, n_subfacets:1,
used:0.0s, Datapath actions: <del>
skb_priority=0,icmp,in_port=1,nw_src=10.0.0.4,nw_dst=10.0.0.3,nw_tos=0,nw_ecn=0,nw_ttl=64,
n_subfacets:1, used:0.0s, Datapath actions: <del>
+skb_priority=0,ip,in_port=1,nw_src=10.0.0.0/30,nw_frag=no, n_subfacets:1,
used:0.0s, Datapath actions: <del>
])
OVS_VSWITCHD_STOP
AT_CLEANUP
--
1.7.10.4
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
