I accidentally sent the wrong version with a typo in the subject and small
wording problems below:
> On Jun 4, 2014, at 5:42 PM, Jarno Rajahalme <jrajaha...@nicira.com> wrote:
>
> When reaching the end
leaf
> of a prefix trie, we checked one bit off the end
> to the
of the
> intended data. However, since the trie node in that case has
> NULLs for both edge links, this did not result in incorrect
> functionality.
>
> Signed-off-by: Jarno Rajahalme <jrajaha...@nicira.com>
> ---
> lib/classifier.c | 28 +++++++++++++++++-----------
> 1 file changed, 17 insertions(+), 11 deletions(-)
>
> diff --git a/lib/classifier.c b/lib/classifier.c
> index 00d47ac..a668df4 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,33 @@ 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) {
> + break;
> }
> + 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;
> + *checkbits = !prev || trie_is_leaf(prev) ? ofs : ofs + 1;
> return match_len;
> }
>
> @@ -2167,7 +2173,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
