When reaching the end of a prefix trie, we checked one bit off the end
to the intended data. However, since the trie node in that case has
NULLs for both edge links, this did not result in incorrect
functionality.
Found via check-valgrind.
Reported-by: Ben Pfaff <b...@nicira.com>
Signed-off-by: Jarno Rajahalme <jrajaha...@nicira.com>
---
v2: Clarify trie_lookup_value() by returning from the case when ofs >= n_bits.
lib/classifier.c | 32 ++++++++++++++++++++------------
1 file changed, 20 insertions(+), 12 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index 00d47ac..e0b3f5a 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -173,6 +173,7 @@ static unsigned int trie_lookup(const struct cls_trie *,
const struct flow *,
unsigned int *checkbits);
static unsigned int trie_lookup_value(const struct trie_node *,
const ovs_be32 value[],
+ unsigned int value_bits,
unsigned int *checkbits);
static void trie_destroy(struct trie_node *);
static void trie_insert(struct cls_trie *, const struct cls_rule *, int mlen);
@@ -1823,7 +1824,7 @@ find_match_wc(const struct cls_subtable *subtable, const
struct flow *flow,
mask = MINIFLOW_GET_BE32(&subtable->mask.masks, tp_src);
value = ((OVS_FORCE ovs_be32 *)flow)[TP_PORTS_OFS32] & mask;
- trie_lookup_value(subtable->ports_trie, &value, &mbits);
+ trie_lookup_value(subtable->ports_trie, &value, 32, &mbits);
((OVS_FORCE ovs_be32 *)&wc->masks)[TP_PORTS_OFS32] |=
mask & htonl(~0 << (32 - mbits));
@@ -2130,28 +2131,35 @@ trie_next_node(const struct trie_node *node, const
ovs_be32 value[],
*/
static unsigned int
trie_lookup_value(const struct trie_node *node, const ovs_be32 value[],
- unsigned int *checkbits)
+ unsigned int n_bits, unsigned int *checkbits)
{
- unsigned int plen = 0, match_len = 0;
+ unsigned int ofs = 0, match_len = 0;
const struct trie_node *prev = NULL;
- for (; node; prev = node, node = trie_next_node(node, value, plen)) {
+ while (node) {
unsigned int eqbits;
/* Check if this edge can be followed. */
- eqbits = prefix_equal_bits(node->prefix, node->nbits, value, plen);
- plen += eqbits;
+ eqbits = prefix_equal_bits(node->prefix, node->nbits, value, ofs);
+ ofs += eqbits;
if (eqbits < node->nbits) { /* Mismatch, nothing more to be found. */
- /* Bit at offset 'plen' differed. */
- *checkbits = plen + 1; /* Includes the first mismatching bit. */
+ /* Bit at offset 'ofs' differed. */
+ *checkbits = ofs + 1; /* Includes the first mismatching bit. */
return match_len;
}
/* Full match, check if rules exist at this prefix length. */
if (node->n_rules > 0) {
- match_len = plen;
+ match_len = ofs;
+ }
+ prev = node;
+ if (ofs >= n_bits) {
+ *checkbits = n_bits; /* Full prefix. */
+ return match_len;
}
+ node = trie_next_node(node, value, ofs);
}
- /* Dead end, exclude the other branch if it exists. */
- *checkbits = !prev || trie_is_leaf(prev) ? plen : plen + 1;
+ /* node == NULL. Full match so far, but we came to a dead end.
+ * need to exclude the other branch if it exists. */
+ *checkbits = !prev || trie_is_leaf(prev) ? ofs : ofs + 1;
return match_len;
}
@@ -2167,7 +2175,7 @@ trie_lookup(const struct cls_trie *trie, const struct
flow *flow,
if (mf_are_prereqs_ok(mf, flow)) {
return trie_lookup_value(trie->root,
&((ovs_be32 *)flow)[mf->flow_be32ofs],
- checkbits);
+ mf->n_bits, checkbits);
}
*checkbits = 0; /* Value not used in this case. */
return UINT_MAX;
--
1.7.10.4
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
