[ovs-dev] [PATCH 5/5] flow: Add struct flowmap.

Joe Stringer joestringer at nicira.com
Wed Aug 5 20:17:34 UTC 2015


With this full series applied, gcc (Debian 4.9.2-10) 4.9.2:

../lib/classifier-private.h:352:14: warning: crazy programmer

I think this is actually a sparse warning, and I've seen it before but
I have no recollection how we appeased it.

On 5 August 2015 at 10:53, Jarno Rajahalme <jrajahalme at nicira.com> wrote:
> Struct miniflow is now sometimes used just as a map.  Define a new
> struct flowmap for that purpose.  The flowmap is defined as an array of
> maps, and it is automatically sized according to the size of struct
> flow, so it will be easier to maintain in the future.
>
> It would have been tempting to use the existing struct bitmap for this
> purpose. The main reason this is not feasible at the moment is that
> some flowmap algorithms are simpler when it can be assumed that no
> struct flow member requires more bits than can fit to a single map
> unit. The tunnel member already requires more than 32 bits, so the map
> unit needs to be 64 bits wide.
>
> Performance critical algorithms enumerate the flowmap array units
> explicitly, as it is easier for the compiler to optimize, compared to
> the normal iterator.  Without this optimization a classifier lookup
> without wildcard masks would be about 25% slower.
>
> With this more general (and maintainable) algorithm the classifier
> lookups are about 5% slower, when the struct flow actually becomes big
> enough to require a second map.  This negates the performance gained
> in the "Pre-compute stage masks" patch earlier in the series.
>
> Requested-by: Ben Pfaff <blp at nicira.com>
> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
> ---
>  lib/classifier-private.h | 116 ++++++------
>  lib/classifier.c         | 158 +++++++----------
>  lib/classifier.h         |   1 -
>  lib/dpif-netdev.c        |  93 +++-------
>  lib/flow.c               | 349 ++++++++++++++++--------------------
>  lib/flow.h               | 448 +++++++++++++++++++++++++++++++----------------
>  lib/match.c              |   5 +-
>  7 files changed, 600 insertions(+), 570 deletions(-)
>
> diff --git a/lib/classifier-private.h b/lib/classifier-private.h
> index cc255fe..f3b44e9 100644
> --- a/lib/classifier-private.h
> +++ b/lib/classifier-private.h
> @@ -42,7 +42,7 @@ struct cls_subtable {
>      /* These fields are accessed by readers who care about wildcarding. */
>      const tag_type tag;       /* Tag generated from mask for partitioning. */
>      const uint8_t n_indices;                   /* How many indices to use. */
> -    const struct miniflow index_maps[CLS_MAX_INDICES + 1]; /* Stage maps. */
> +    const struct flowmap index_maps[CLS_MAX_INDICES + 1]; /* Stage maps. */
>      unsigned int trie_plen[CLS_MAX_TRIES];  /* Trie prefix length in 'mask'
>                                               * (runtime configurable). */
>      const int ports_mask_len;
> @@ -238,16 +238,16 @@ flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
>      const uint64_t *mask_values = miniflow_get_values(&mask->masks);
>      const uint64_t *flow_u64 = (const uint64_t *)flow;
>      const uint64_t *p = mask_values;
> -    uint32_t hash;
> -    size_t idx;
> +    uint32_t hash = basis;
> +    map_t map;
>
> -    hash = basis;
> -    MAP_FOR_EACH_INDEX(idx, mask->masks.tnl_map) {
> -        hash = hash_add64(hash, flow_u64[idx] & *p++);
> -    }
> -    flow_u64 += FLOW_TNL_U64S;
> -    MAP_FOR_EACH_INDEX(idx, mask->masks.pkt_map) {
> -        hash = hash_add64(hash, flow_u64[idx] & *p++);
> +    FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) {
> +        size_t idx;
> +
> +        MAP_FOR_EACH_INDEX (idx, map) {
> +            hash = hash_add64(hash, flow_u64[idx] & *p++);
> +        }
> +        flow_u64 += MAP_T_BITS;
>      }
>
>      return hash_finish(hash, (p - mask_values) * 8);
> @@ -265,13 +265,10 @@ miniflow_hash_in_minimask(const struct miniflow *flow,
>      const uint64_t *mask_values = miniflow_get_values(&mask->masks);
>      const uint64_t *p = mask_values;
>      uint32_t hash = basis;
> -    uint64_t flow_u64;
> +    uint64_t value;
>
> -    MINIFLOW_FOR_EACH_IN_TNL_MAP(flow_u64, flow, mask->masks) {
> -        hash = hash_add64(hash, flow_u64 & *p++);
> -    }
> -    MINIFLOW_FOR_EACH_IN_PKT_MAP(flow_u64, flow, mask->masks) {
> -        hash = hash_add64(hash, flow_u64 & *p++);
> +    MINIFLOW_FOR_EACH_IN_FLOWMAP(value, flow, mask->masks.map) {
> +        hash = hash_add64(hash, value & *p++);
>      }
>
>      return hash_finish(hash, (p - mask_values) * 8);
> @@ -285,24 +282,23 @@ miniflow_hash_in_minimask(const struct miniflow *flow,
>  static inline uint32_t
>  flow_hash_in_minimask_range(const struct flow *flow,
>                              const struct minimask *mask,
> -                            const struct miniflow *maps,
> +                            const struct flowmap fmap,
>                              unsigned int *offset,
>                              uint32_t *basis)
>  {
>      const uint64_t *mask_values = miniflow_get_values(&mask->masks);
> -    const uint64_t *p = mask_values + *offset;
>      const uint64_t *flow_u64 = (const uint64_t *)flow;
> +    const uint64_t *p = mask_values + *offset;
>      uint32_t hash = *basis;
> -    size_t idx;
> +    map_t map;
>
> -    if (OVS_UNLIKELY(maps->tnl_map)) {
> -        MAP_FOR_EACH_INDEX(idx, maps->tnl_map) {
> +    FLOWMAP_FOR_EACH_MAP (map, fmap) {
> +        size_t idx;
> +
> +        MAP_FOR_EACH_INDEX (idx, map) {
>              hash = hash_add64(hash, flow_u64[idx] & *p++);
>          }
> -    }
> -    flow_u64 += FLOW_TNL_U64S;
> -    MAP_FOR_EACH_INDEX(idx, maps->pkt_map) {
> -        hash = hash_add64(hash, flow_u64[idx] & *p++);
> +        flow_u64 += MAP_T_BITS;
>      }
>
>      *basis = hash; /* Allow continuation from the unfinished value. */
> @@ -324,20 +320,19 @@ flow_wildcards_fold_minimask(struct flow_wildcards *wc,
>  static inline void
>  flow_wildcards_fold_minimask_in_map(struct flow_wildcards *wc,
>                                      const struct minimask *mask,
> -                                    const struct miniflow *map)
> +                                    const struct flowmap fmap)
>  {
>      const uint64_t *p = miniflow_get_values(&mask->masks);
>      uint64_t *dst_u64 = (uint64_t *)&wc->masks;
> -    size_t idx;
> +    map_t map;
> +
> +    FLOWMAP_FOR_EACH_MAP (map, fmap) {
> +        size_t idx;
>
> -    if (map->tnl_map) {
> -        MAP_FOR_EACH_INDEX(idx, map->tnl_map) {
> +        MAP_FOR_EACH_INDEX (idx, map) {
>              dst_u64[idx] |= *p++;
>          }
> -    }
> -    dst_u64 += FLOW_TNL_U64S;
> -    MAP_FOR_EACH_INDEX(idx, map->pkt_map) {
> -        dst_u64[idx] |= *p++;
> +        dst_u64 += MAP_T_BITS;
>      }
>  }
>
> @@ -348,25 +343,21 @@ miniflow_hash(const struct miniflow *flow, uint32_t basis)
>      const uint64_t *values = miniflow_get_values(flow);
>      const uint64_t *p = values;
>      uint32_t hash = basis;
> -    uint64_t hash_tnl_map = 0, hash_pkt_map = 0;
> -    uint64_t map;
> +    struct flowmap hash_map;
> +    map_t map;
> +    size_t idx;
>
> -    for (map = flow->tnl_map; map; map = zero_rightmost_1bit(map)) {
> +    flowmap_init(&hash_map);
> +    FLOWMAP_FOR_EACH_INDEX (idx, flow->map) {
>          if (*p) {
>              hash = hash_add64(hash, *p);
> -            hash_tnl_map |= rightmost_1bit(map);
> +            flowmap_set(&hash_map, idx, 1);
>          }
>          p++;
>      }
> -    for (map = flow->pkt_map; map; map = zero_rightmost_1bit(map)) {
> -        if (*p) {
> -            hash = hash_add64(hash, *p);
> -            hash_pkt_map |= rightmost_1bit(map);
> -        }
> -        p++;
> +    FLOWMAP_FOR_EACH_MAP (map, hash_map) {
> +        hash = hash_add64(hash, map);
>      }
> -    hash = hash_add64(hash, hash_tnl_map);
> -    hash = hash_add64(hash, hash_pkt_map);
>
>      return hash_finish(hash, p - values);
>  }
> @@ -375,14 +366,20 @@ miniflow_hash(const struct miniflow *flow, uint32_t basis)
>  static inline uint32_t
>  minimask_hash(const struct minimask *mask, uint32_t basis)
>  {
> -    return miniflow_hash(&mask->masks, basis);
> -}
> +    const uint64_t *values = miniflow_get_values(&mask->masks);
> +    const uint64_t *p = values;
> +    uint32_t hash = basis;
> +    map_t map;
> +    const uint64_t *end = values + miniflow_n_values(&mask->masks);
>
> -/* Returns a hash value for 'match', given 'basis'. */
> -static inline uint32_t
> -minimatch_hash(const struct minimatch *match, uint32_t basis)
> -{
> -    return miniflow_hash(match->flow, minimask_hash(match->mask, basis));
> +    while (p < end) {
> +        hash = hash_add64(hash, *p++);
> +    }
> +    FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) {
> +        hash = hash_add64(hash, map);
> +    }
> +
> +    return hash_finish(hash, p - values);
>  }
>
>  /* Returns a hash value for the bits of range [start, end) in 'minimatch',
> @@ -392,20 +389,15 @@ minimatch_hash(const struct minimatch *match, uint32_t basis)
>   * flow_hash_in_minimask_range(), only the form of the arguments differ. */
>  static inline uint32_t
>  minimatch_hash_range(const struct minimatch *match,
> -                     const struct miniflow *maps, unsigned int *offset,
> +                     const struct flowmap map, unsigned int *offset,
>                       uint32_t *basis)
>  {
> -    const uint64_t *p = miniflow_get_values(match->flow);
> -    const uint64_t *q = miniflow_get_values(&match->mask->masks);
> +    const uint64_t *p = miniflow_get_values(match->flow) + *offset;
> +    const uint64_t *q = miniflow_get_values(&match->mask->masks) + *offset;
>      uint32_t hash = *basis;
> -    int n, i;
> -
> -    n = miniflow_n_values(maps);
> -
> -    q += *offset;
> -    p += *offset;
> +    int n = flowmap_n_1bits(map);
>
> -    for (i = 0; i < n; i++) {
> +    for (int i = 0; i < n; i++) {
>          hash = hash_add64(hash, p[i] & q[i]);
>      }
>      *basis = hash; /* Allow continuation from the unfinished value. */
> diff --git a/lib/classifier.c b/lib/classifier.c
> index 975d04f..fb5e6e8 100644
> --- a/lib/classifier.c
> +++ b/lib/classifier.c
> @@ -262,13 +262,6 @@ cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b)
>      return a->priority == b->priority && minimatch_equal(&a->match, &b->match);
>  }
>
> -/* Returns a hash value for 'rule', folding in 'basis'. */
> -uint32_t
> -cls_rule_hash(const struct cls_rule *rule, uint32_t basis)
> -{
> -    return minimatch_hash(&rule->match, hash_int(rule->priority, basis));
> -}
> -
>  /* Appends a string describing 'rule' to 's'. */
>  void
>  cls_rule_format(const struct cls_rule *rule, struct ds *s)
> @@ -600,10 +593,10 @@ classifier_replace(struct classifier *cls, const struct cls_rule *rule,
>      basis = 0;
>      mask_offset = 0;
>      for (i = 0; i < subtable->n_indices; i++) {
> -        ihash[i] = minimatch_hash_range(&rule->match, &subtable->index_maps[i],
> +        ihash[i] = minimatch_hash_range(&rule->match, subtable->index_maps[i],
>                                          &mask_offset, &basis);
>      }
> -    hash = minimatch_hash_range(&rule->match, &subtable->index_maps[i],
> +    hash = minimatch_hash_range(&rule->match, subtable->index_maps[i],
>                                  &mask_offset, &basis);
>
>      head = find_equal(subtable, rule->match.flow, hash);
> @@ -804,10 +797,10 @@ classifier_remove(struct classifier *cls, const struct cls_rule *cls_rule)
>      mask_offset = 0;
>      for (i = 0; i < subtable->n_indices; i++) {
>          ihash[i] = minimatch_hash_range(&cls_rule->match,
> -                                        &subtable->index_maps[i],
> +                                        subtable->index_maps[i],
>                                          &mask_offset, &basis);
>      }
> -    hash = minimatch_hash_range(&cls_rule->match, &subtable->index_maps[i],
> +    hash = minimatch_hash_range(&cls_rule->match, subtable->index_maps[i],
>                                  &mask_offset, &basis);
>
>      head = find_equal(subtable, cls_rule->match.flow, hash);
> @@ -1532,40 +1525,32 @@ find_subtable(const struct classifier *cls, const struct minimask *mask)
>  /* Initializes 'map' with a subset of 'miniflow''s maps that includes only the
>   * portions with u64-offset 'i' such that 'start' <= i < 'end'.  Does not copy
>   * any data from 'miniflow' to 'map'. */
> -static void
> -miniflow_get_map_in_range(const struct miniflow *miniflow,
> -                          uint8_t start, uint8_t end, struct miniflow *map)
> +static struct flowmap
> +miniflow_get_map_in_range(const struct miniflow *miniflow, uint8_t start,
> +                          uint8_t end)
>  {
> -    *map = *miniflow;   /* Copy maps. */
> -
> -    if (start >= FLOW_TNL_U64S) {
> -        map->tnl_map = 0;
> -        if (start > FLOW_TNL_U64S) {
> -            /* Clear 'start - FLOW_TNL_U64S' LSBs from pkt_map. */
> -            start -= FLOW_TNL_U64S;
> -            uint64_t msk = (UINT64_C(1) << start) - 1;
> +    struct flowmap map;
> +    size_t ofs = 0;
>
> -            map->pkt_map &= ~msk;
> -        }
> -    } else if (start > 0) {
> -        /* Clear 'start' LSBs from tnl_map. */
> -        uint64_t msk = (UINT64_C(1) << start) - 1;
> +    map = miniflow->map;
>
> -        map->tnl_map &= ~msk;
> +    /* Clear the bits before 'start'. */
> +    while (start >= MAP_T_BITS) {
> +        start -= MAP_T_BITS;
> +        ofs += MAP_T_BITS;
> +        map.bits[start / MAP_T_BITS] = 0;
> +    }
> +    if (start > 0) {
> +        flowmap_clear(&map, ofs, start);
>      }
>
> -    if (end <= FLOW_TNL_U64S) {
> -        map->pkt_map = 0;
> -        if (end < FLOW_TNL_U64S) {
> -            /* Keep 'end' LSBs in tnl_map. */
> -            map->tnl_map &= (UINT64_C(1) << end) - 1;
> -        }
> -    } else {
> -        if (end < FLOW_U64S) {
> -            /* Keep 'end - FLOW_TNL_U64S' LSBs in pkt_map. */
> -            map->pkt_map &= (UINT64_C(1) << (end - FLOW_TNL_U64S)) - 1;
> -        }
> +    /* Clear the bits starting at 'end'. */
> +    if (end < FLOW_U64S) {
> +        /* flowmap_clear() can handle at most MAP_T_BITS at a time. */
> +        ovs_assert(FLOW_U64S - end <= MAP_T_BITS);
> +        flowmap_clear(&map, end, FLOW_U64S - end);
>      }
> +    return map;
>  }
>
>  /* The new subtable will be visible to the readers only after this. */
> @@ -1575,7 +1560,7 @@ insert_subtable(struct classifier *cls, const struct minimask *mask)
>      uint32_t hash = minimask_hash(mask, 0);
>      struct cls_subtable *subtable;
>      int i, index = 0;
> -    struct minimask stage_mask;
> +    struct flowmap stage_map;
>      uint8_t prev;
>      size_t count = miniflow_n_values(&mask->masks);
>
> @@ -1587,26 +1572,25 @@ insert_subtable(struct classifier *cls, const struct minimask *mask)
>      /* Init indices for segmented lookup, if any. */
>      prev = 0;
>      for (i = 0; i < cls->n_flow_segments; i++) {
> -        miniflow_get_map_in_range(&mask->masks, prev, cls->flow_segments[i],
> -                                  &stage_mask.masks);
> +        stage_map = miniflow_get_map_in_range(&mask->masks, prev,
> +                                              cls->flow_segments[i]);
>          /* Add an index if it adds mask bits. */
> -        if (!minimask_is_catchall(&stage_mask)) {
> +        if (!flowmap_is_empty(stage_map)) {
>              cmap_init(&subtable->indices[index]);
> -            *CONST_CAST(struct miniflow *, &subtable->index_maps[index])
> -                = stage_mask.masks;
> +            *CONST_CAST(struct flowmap *, &subtable->index_maps[index])
> +                = stage_map;
>              index++;
>          }
>          prev = cls->flow_segments[i];
>      }
>      /* Map for the final stage. */
> -    miniflow_get_map_in_range(
> -        &mask->masks, prev, FLOW_U64S,
> -        CONST_CAST(struct miniflow *, &subtable->index_maps[index]));
> +    *CONST_CAST(struct flowmap *, &subtable->index_maps[index])
> +        = miniflow_get_map_in_range(&mask->masks, prev, FLOW_U64S);
>      /* Check if the final stage adds any bits,
>       * and remove the last index if it doesn't. */
>      if (index > 0) {
> -        if (miniflow_equal_maps(&subtable->index_maps[index],
> -                                &subtable->index_maps[index - 1])) {
> +        if (flowmap_equal(subtable->index_maps[index],
> +                          subtable->index_maps[index - 1])) {
>              --index;
>              cmap_destroy(&subtable->indices[index]);
>          }
> @@ -1665,7 +1649,7 @@ static unsigned int be_get_bit_at(const ovs_be32 value[], unsigned int ofs);
>  static inline bool
>  check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
>              const unsigned int field_plen[CLS_MAX_TRIES],
> -            const struct miniflow *range_map, const struct flow *flow,
> +            const struct flowmap range_map, const struct flow *flow,
>              struct flow_wildcards *wc)
>  {
>      int j;
> @@ -1681,7 +1665,7 @@ check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
>              uint8_t be64ofs = be32ofs / 2;
>
>              /* Is the trie field within the current range of fields? */
> -            if (MINIFLOW_IN_MAP(range_map, be64ofs)) {
> +            if (FLOWMAP_IS_SET(range_map, be64ofs)) {
>                  /* On-demand trie lookup. */
>                  if (!ctx->lookup_done) {
>                      memset(&ctx->match_plens, 0, sizeof ctx->match_plens);
> @@ -1736,20 +1720,18 @@ miniflow_and_mask_matches_flow(const struct miniflow *flow,
>      const uint64_t *flowp = miniflow_get_values(flow);
>      const uint64_t *maskp = miniflow_get_values(&mask->masks);
>      const uint64_t *target_u64 = (const uint64_t *)target;
> -    size_t idx;
> +    map_t map;
>
> -    MAP_FOR_EACH_INDEX(idx, mask->masks.tnl_map) {
> -        if ((*flowp++ ^ target_u64[idx]) & *maskp++) {
> -            return false;
> -        }
> -    }
> -    target_u64 += FLOW_TNL_U64S;
> -    MAP_FOR_EACH_INDEX(idx, mask->masks.pkt_map) {
> -        if ((*flowp++ ^ target_u64[idx]) & *maskp++) {
> -            return false;
> +    FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) {
> +        size_t idx;
> +
> +        MAP_FOR_EACH_INDEX (idx, map) {
> +            if ((*flowp++ ^ target_u64[idx]) & *maskp++) {
> +                return false;
> +            }
>          }
> +        target_u64 += MAP_T_BITS;
>      }
> -
>      return true;
>  }
>
> @@ -1792,33 +1774,24 @@ miniflow_and_mask_matches_flow_wc(const struct miniflow *flow,
>      const uint64_t *target_u64 = (const uint64_t *)target;
>      uint64_t *wc_u64 = (uint64_t *)&wc->masks;
>      uint64_t diff;
> +    map_t map;
>      size_t idx;
>
> -    MAP_FOR_EACH_INDEX(idx, mask->masks.tnl_map) {
> -        uint64_t msk = *maskp++;
> +    FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) {
> +        MAP_FOR_EACH_INDEX(idx, map) {
> +            uint64_t msk = *maskp++;
>
> -        diff = (*flowp++ ^ target_u64[idx]) & msk;
> -        if (diff) {
> -            goto out;
> -        }
> -
> -        /* Fill in the bits that were looked at. */
> -        wc_u64[idx] |= msk;
> -    }
> -    target_u64 += FLOW_TNL_U64S;
> -    wc_u64 += FLOW_TNL_U64S;
> -    MAP_FOR_EACH_INDEX(idx, mask->masks.pkt_map) {
> -        uint64_t msk = *maskp++;
> +            diff = (*flowp++ ^ target_u64[idx]) & msk;
> +            if (diff) {
> +                goto out;
> +            }
>
> -        diff = (*flowp++ ^ target_u64[idx]) & msk;
> -        if (diff) {
> -            goto out;
> +            /* Fill in the bits that were looked at. */
> +            wc_u64[idx] |= msk;
>          }
> -
> -        /* Fill in the bits that were looked at. */
> -        wc_u64[idx] |= msk;
> +        target_u64 += MAP_T_BITS;
> +        wc_u64 += MAP_T_BITS;
>      }
> -
>      return true;
>
>  out:
> @@ -1840,7 +1813,7 @@ find_match_wc(const struct cls_subtable *subtable, cls_version_t version,
>      uint32_t basis = 0, hash;
>      const struct cls_match *rule = NULL;
>      int i;
> -    struct miniflow stages_map;
> +    struct flowmap stages_map;
>      unsigned int mask_offset = 0;
>
>      if (OVS_UNLIKELY(!wc)) {
> @@ -1848,24 +1821,23 @@ find_match_wc(const struct cls_subtable *subtable, cls_version_t version,
>                            flow_hash_in_minimask(flow, &subtable->mask, 0));
>      }
>
> -    memset(&stages_map, 0, sizeof stages_map);
> +    flowmap_init(&stages_map);
>      /* Try to finish early by checking fields in segments. */
>      for (i = 0; i < subtable->n_indices; i++) {
>          const struct cmap_node *inode;
>
>          if (check_tries(trie_ctx, n_tries, subtable->trie_plen,
> -                        &subtable->index_maps[i], flow, wc)) {
> +                        subtable->index_maps[i], flow, wc)) {
>              /* 'wc' bits for the trie field set, now unwildcard the preceding
>               * bits used so far. */
>              goto no_match;
>          }
>
>          /* Accumulate the map used so far. */
> -        stages_map.tnl_map |= subtable->index_maps[i].tnl_map;
> -        stages_map.pkt_map |= subtable->index_maps[i].pkt_map;
> +        stages_map = flowmap_or(stages_map, subtable->index_maps[i]);
>
>          hash = flow_hash_in_minimask_range(flow, &subtable->mask,
> -                                           &subtable->index_maps[i],
> +                                           subtable->index_maps[i],
>                                             &mask_offset, &basis);
>
>          inode = cmap_find(&subtable->indices[i], hash);
> @@ -1897,11 +1869,11 @@ find_match_wc(const struct cls_subtable *subtable, cls_version_t version,
>      }
>      /* Trie check for the final range. */
>      if (check_tries(trie_ctx, n_tries, subtable->trie_plen,
> -                    &subtable->index_maps[i], flow, wc)) {
> +                    subtable->index_maps[i], flow, wc)) {
>          goto no_match;
>      }
>      hash = flow_hash_in_minimask_range(flow, &subtable->mask,
> -                                       &subtable->index_maps[i],
> +                                       subtable->index_maps[i],
>                                         &mask_offset, &basis);
>      rule = find_match(subtable, version, flow, hash);
>      if (!rule && subtable->ports_mask_len) {
> @@ -1928,7 +1900,7 @@ find_match_wc(const struct cls_subtable *subtable, cls_version_t version,
>  no_match:
>      /* Unwildcard the bits in stages so far, as they were used in determining
>       * there is no match. */
> -    flow_wildcards_fold_minimask_in_map(wc, &subtable->mask, &stages_map);
> +    flow_wildcards_fold_minimask_in_map(wc, &subtable->mask, stages_map);
>      return NULL;
>  }
>
> diff --git a/lib/classifier.h b/lib/classifier.h
> index 5ffe756..889dc1e 100644
> --- a/lib/classifier.h
> +++ b/lib/classifier.h
> @@ -372,7 +372,6 @@ void cls_rule_set_conjunctions(struct cls_rule *,
>                                 const struct cls_conjunction *, size_t n);
>
>  bool cls_rule_equal(const struct cls_rule *, const struct cls_rule *);
> -uint32_t cls_rule_hash(const struct cls_rule *, uint32_t basis);
>  void cls_rule_format(const struct cls_rule *, struct ds *);
>  bool cls_rule_is_catchall(const struct cls_rule *);
>  bool cls_rule_is_loose_match(const struct cls_rule *rule,
> diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
> index 83e55e7..357b750 100644
> --- a/lib/dpif-netdev.c
> +++ b/lib/dpif-netdev.c
> @@ -488,15 +488,12 @@ emc_cache_init(struct emc_cache *flow_cache)
>  {
>      int i;
>
> -    BUILD_ASSERT(sizeof(struct miniflow) == 2 * sizeof(uint64_t));
> -
>      flow_cache->sweep_idx = 0;
>      for (i = 0; i < ARRAY_SIZE(flow_cache->entries); i++) {
>          flow_cache->entries[i].flow = NULL;
>          flow_cache->entries[i].key.hash = 0;
>          flow_cache->entries[i].key.len = sizeof(struct miniflow);
> -        flow_cache->entries[i].key.mf.tnl_map = 0;
> -        flow_cache->entries[i].key.mf.pkt_map = 0;
> +        flowmap_init(&flow_cache->entries[i].key.mf.map);
>      }
>  }
>
> @@ -1521,12 +1518,7 @@ static bool dp_netdev_flow_ref(struct dp_netdev_flow *flow)
>   *   miniflow_extract(), if the map is different the miniflow is different.
>   *   Therefore we can be faster by comparing the map and the miniflow in a
>   *   single memcmp().
> - * - These functions can be inlined by the compiler.
> - *
> - * The following assertions make sure that what we're doing with miniflow is
> - * safe.
> - */
> -BUILD_ASSERT_DECL(sizeof(struct miniflow) == 2 * sizeof(uint64_t));
> + * - These functions can be inlined by the compiler. */
>
>  /* Given the number of bits set in miniflow's maps, returns the size of the
>   * 'netdev_flow_key.mf' */
> @@ -1585,47 +1577,32 @@ static inline void
>  netdev_flow_mask_init(struct netdev_flow_key *mask,
>                        const struct match *match)
>  {
> -    const uint64_t *mask_u64 = (const uint64_t *) &match->wc.masks;
>      uint64_t *dst = miniflow_values(&mask->mf);
> -    struct miniflow maps;
> -    uint64_t map;
> +    struct flowmap fmap;
>      uint32_t hash = 0;
> -    int n;
> +    size_t idx;
>
>      /* Only check masks that make sense for the flow. */
> -    flow_wc_map(&match->flow, &maps);
> -    memset(&mask->mf, 0, sizeof mask->mf);   /* Clear maps. */
> +    flow_wc_map(&match->flow, &fmap);
> +    flowmap_init(&mask->mf.map);
>
> -    map = maps.tnl_map;
> -    while (map) {
> -        uint64_t rm1bit = rightmost_1bit(map);
> -        int i = raw_ctz(map);
> +    FLOWMAP_FOR_EACH_INDEX(idx, fmap) {
> +        uint64_t mask_u64 = flow_u64_value(&match->wc.masks, idx);
>
> -        if (mask_u64[i]) {
> -            mask->mf.tnl_map |= rm1bit;
> -            *dst++ = mask_u64[i];
> -            hash = hash_add64(hash, mask_u64[i]);
> +        if (mask_u64) {
> +            flowmap_set(&mask->mf.map, idx, 1);
> +            *dst++ = mask_u64;
> +            hash = hash_add64(hash, mask_u64);
>          }
> -        map -= rm1bit;
>      }
> -    mask_u64 += FLOW_TNL_U64S;
> -    map = maps.pkt_map;
> -    while (map) {
> -        uint64_t rm1bit = rightmost_1bit(map);
> -        int i = raw_ctz(map);
>
> -        if (mask_u64[i]) {
> -            mask->mf.pkt_map |= rm1bit;
> -            *dst++ = mask_u64[i];
> -            hash = hash_add64(hash, mask_u64[i]);
> -        }
> -        map -= rm1bit;
> -    }
> +    map_t map;
>
> -    hash = hash_add64(hash, mask->mf.tnl_map);
> -    hash = hash_add64(hash, mask->mf.pkt_map);
> +    FLOWMAP_FOR_EACH_MAP (map, mask->mf.map) {
> +        hash = hash_add64(hash, map);
> +    }
>
> -    n = dst - miniflow_get_values(&mask->mf);
> +    size_t n = dst - miniflow_get_values(&mask->mf);
>
>      mask->hash = hash_finish(hash, n * 8);
>      mask->len = netdev_flow_key_size(n);
> @@ -1645,7 +1622,7 @@ netdev_flow_key_init_masked(struct netdev_flow_key *dst,
>      dst->len = mask->len;
>      dst->mf = mask->mf;   /* Copy maps. */
>
> -    FLOW_FOR_EACH_IN_MAPS(value, flow, mask->mf) {
> +    FLOW_FOR_EACH_IN_MAPS(value, flow, mask->mf.map) {
>          *dst_u64 = value & *mask_u64++;
>          hash = hash_add64(hash, *dst_u64++);
>      }
> @@ -1653,13 +1630,9 @@ netdev_flow_key_init_masked(struct netdev_flow_key *dst,
>                              (dst_u64 - miniflow_get_values(&dst->mf)) * 8);
>  }
>
> -/* Iterate through netdev_flow_key TNL u64 values specified by 'MAPS'. */
> -#define NETDEV_FLOW_KEY_FOR_EACH_IN_TNL_MAP(VALUE, KEY, MAPS)   \
> -    MINIFLOW_FOR_EACH_IN_TNL_MAP(VALUE, &(KEY)->mf, MAPS)
> -
> -/* Iterate through netdev_flow_key PKT u64 values specified by 'MAPS'. */
> -#define NETDEV_FLOW_KEY_FOR_EACH_IN_PKT_MAP(VALUE, KEY, MAPS)   \
> -    MINIFLOW_FOR_EACH_IN_PKT_MAP(VALUE, &(KEY)->mf, MAPS)
> +/* Iterate through netdev_flow_key TNL u64 values specified by 'FLOWMAP'. */
> +#define NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(VALUE, KEY, FLOWMAP)   \
> +    MINIFLOW_FOR_EACH_IN_FLOWMAP(VALUE, &(KEY)->mf, FLOWMAP)
>
>  /* Returns a hash value for the bits of 'key' where there are 1-bits in
>   * 'mask'. */
> @@ -1669,13 +1642,10 @@ netdev_flow_key_hash_in_mask(const struct netdev_flow_key *key,
>  {
>      const uint64_t *p = miniflow_get_values(&mask->mf);
>      uint32_t hash = 0;
> -    uint64_t key_u64;
> +    uint64_t value;
>
> -    NETDEV_FLOW_KEY_FOR_EACH_IN_TNL_MAP(key_u64, key, mask->mf) {
> -        hash = hash_add64(hash, key_u64 & *p++);
> -    }
> -    NETDEV_FLOW_KEY_FOR_EACH_IN_PKT_MAP(key_u64, key, mask->mf) {
> -        hash = hash_add64(hash, key_u64 & *p++);
> +    NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(value, key, mask->mf.map) {
> +        hash = hash_add64(hash, value & *p++);
>      }
>
>      return hash_finish(hash, (p - miniflow_get_values(&mask->mf)) * 8);
> @@ -2008,8 +1978,8 @@ dp_netdev_flow_add(struct dp_netdev_pmd_thread *pmd,
>
>      netdev_flow_mask_init(&mask, match);
>      /* Make sure wc does not have metadata. */
> -    ovs_assert(!(mask.mf.pkt_map
> -                 & (MINIFLOW_PKT_MAP(metadata) | MINIFLOW_PKT_MAP(regs))));
> +    ovs_assert(!FLOWMAP_HAS_FIELD(&mask.mf.map, metadata)
> +               && !FLOWMAP_HAS_FIELD(&mask.mf.map, regs));
>
>      /* Do not allocate extra space. */
>      flow = xmalloc(sizeof *flow - sizeof flow->cr.flow.mf + mask.len);
> @@ -3886,15 +3856,10 @@ dpcls_rule_matches_key(const struct dpcls_rule *rule,
>  {
>      const uint64_t *keyp = miniflow_get_values(&rule->flow.mf);
>      const uint64_t *maskp = miniflow_get_values(&rule->mask->mf);
> -    uint64_t target_u64;
> +    uint64_t value;
>
> -    NETDEV_FLOW_KEY_FOR_EACH_IN_TNL_MAP(target_u64, target, rule->flow.mf) {
> -        if (OVS_UNLIKELY((target_u64 & *maskp++) != *keyp++)) {
> -            return false;
> -        }
> -    }
> -    NETDEV_FLOW_KEY_FOR_EACH_IN_PKT_MAP(target_u64, target, rule->flow.mf) {
> -        if (OVS_UNLIKELY((target_u64 & *maskp++) != *keyp++)) {
> +    NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(value, target, rule->flow.mf.map) {
> +        if (OVS_UNLIKELY((value & *maskp++) != *keyp++)) {
>              return false;
>          }
>      }
> diff --git a/lib/flow.c b/lib/flow.c
> index 9a2bb6b..091282e 100644
> --- a/lib/flow.c
> +++ b/lib/flow.c
> @@ -112,7 +112,7 @@ data_try_pull(const void **datap, size_t *sizep, size_t size)
>
>  /* Context for pushing data to a miniflow. */
>  struct mf_ctx {
> -    struct miniflow maps;
> +    struct flowmap map;
>      uint64_t *data;
>      uint64_t * const end;
>  };
> @@ -132,114 +132,93 @@ BUILD_MESSAGE("FLOW_WC_SEQ changed: miniflow_extract() will have runtime "
>  #define MINIFLOW_ASSERT(X)
>  #endif
>
> -#define miniflow_set_map(MF, OFS)                                       \
> +/* True if 'IDX' and higher bits are not set. */
> +#define ASSERT_FLOWMAP_NOT_SET(FM, IDX)                                 \
>  {                                                                       \
> -    size_t ofs = (OFS);                                                 \
> -                                                                        \
> -    if (ofs < FLOW_TNL_U64S) {                                          \
> -        MINIFLOW_ASSERT(!(MF.maps.tnl_map & (UINT64_MAX << ofs))        \
> -                        && !MF.maps.pkt_map);                           \
> -        MF.maps.tnl_map |= UINT64_C(1) << ofs;                          \
> -    } else {                                                            \
> -        ofs -= FLOW_TNL_U64S;                                           \
> -        MINIFLOW_ASSERT(!(MF.maps.pkt_map & (UINT64_MAX << ofs)));      \
> -        MF.maps.pkt_map |= UINT64_C(1) << ofs;                          \
> +    MINIFLOW_ASSERT(!((FM)->bits[(IDX) / MAP_T_BITS] &                  \
> +                      (FLOWMAP_MAX << ((IDX) % MAP_T_BITS))));          \
> +    for (size_t i = (IDX) / MAP_T_BITS + 1; i < FLOWMAP_UNITS; i++) {   \
> +        MINIFLOW_ASSERT(!(FM)->bits[i]);                                \
>      }                                                                   \
>  }
>
> -#define miniflow_assert_in_map(MF, OFS)                                 \
> -{                                                                       \
> -    size_t ofs = (OFS);                                                 \
> -                                                                        \
> -    if (ofs < FLOW_TNL_U64S) {                                          \
> -        MINIFLOW_ASSERT(MF.maps.tnl_map & UINT64_C(1) << ofs            \
> -                        && !(MF.maps.tnl_map & UINT64_MAX << (ofs + 1)) \
> -                        && !MF.maps.pkt_map);                           \
> -    } else {                                                            \
> -        ofs -= FLOW_TNL_U64S;                                           \
> -        MINIFLOW_ASSERT(MF.maps.pkt_map & UINT64_C(1) << ofs            \
> -                        && !(MF.maps.pkt_map & UINT64_MAX << (ofs + 1))); \
> -    }                                                                   \
> +#define miniflow_set_map(MF, OFS)            \
> +    {                                        \
> +    ASSERT_FLOWMAP_NOT_SET(&MF.map, (OFS));  \
> +    flowmap_set(&MF.map, (OFS), 1);          \
>  }
>
> -#define miniflow_push_uint64_(MF, OFS, VALUE)                           \
> -{                                                                       \
> -    MINIFLOW_ASSERT(MF.data < MF.end && (OFS) % 8 == 0);                \
> -    *MF.data++ = VALUE;                                                 \
> -    miniflow_set_map(MF, OFS / 8);                                          \
> +#define miniflow_assert_in_map(MF, OFS)             \
> +    MINIFLOW_ASSERT(FLOWMAP_IS_SET(MF.map, (OFS))); \
> +    ASSERT_FLOWMAP_NOT_SET(&MF.map, (OFS) + 1)
> +
> +#define miniflow_push_uint64_(MF, OFS, VALUE)              \
> +{                                                          \
> +    MINIFLOW_ASSERT(MF.data < MF.end && (OFS) % 8 == 0);   \
> +    *MF.data++ = VALUE;                                    \
> +    miniflow_set_map(MF, OFS / 8);                         \
>  }
>
> -#define miniflow_push_be64_(MF, OFS, VALUE) \
> +#define miniflow_push_be64_(MF, OFS, VALUE)                     \
>      miniflow_push_uint64_(MF, OFS, (OVS_FORCE uint64_t)(VALUE))
>
> -#define miniflow_push_uint32_(MF, OFS, VALUE)                           \
> -    {                                                                   \
> -    MINIFLOW_ASSERT(MF.data < MF.end);                                  \
> -                                                                        \
> -    if ((OFS) % 8 == 0) {                                               \
> -        miniflow_set_map(MF, OFS / 8);                                  \
> -        *(uint32_t *)MF.data = VALUE;                                   \
> -    } else if ((OFS) % 8 == 4) {                                        \
> -        miniflow_assert_in_map(MF, OFS / 8);                            \
> -        *((uint32_t *)MF.data + 1) = VALUE;                             \
> -        MF.data++;                                                      \
> -    }                                                                   \
> +#define miniflow_push_uint32_(MF, OFS, VALUE)   \
> +    {                                           \
> +    MINIFLOW_ASSERT(MF.data < MF.end);          \
> +                                                \
> +    if ((OFS) % 8 == 0) {                       \
> +        miniflow_set_map(MF, OFS / 8);          \
> +        *(uint32_t *)MF.data = VALUE;           \
> +    } else if ((OFS) % 8 == 4) {                \
> +        miniflow_assert_in_map(MF, OFS / 8);    \
> +        *((uint32_t *)MF.data + 1) = VALUE;     \
> +        MF.data++;                              \
> +    }                                           \
>  }
>
>  #define miniflow_push_be32_(MF, OFS, VALUE)                     \
>      miniflow_push_uint32_(MF, OFS, (OVS_FORCE uint32_t)(VALUE))
>
> -#define miniflow_push_uint16_(MF, OFS, VALUE)                           \
> -{                                                                       \
> -    MINIFLOW_ASSERT(MF.data < MF.end);                                  \
> -                                                                        \
> -    if ((OFS) % 8 == 0) {                                               \
> -        miniflow_set_map(MF, OFS / 8);                                  \
> -        *(uint16_t *)MF.data = VALUE;                                   \
> -    } else if ((OFS) % 8 == 2) {                                        \
> -        miniflow_assert_in_map(MF, OFS / 8);                            \
> -        *((uint16_t *)MF.data + 1) = VALUE;                             \
> -    } else if ((OFS) % 8 == 4) {                                        \
> -        miniflow_assert_in_map(MF, OFS / 8);                            \
> -        *((uint16_t *)MF.data + 2) = VALUE;                             \
> -    } else if ((OFS) % 8 == 6) {                                        \
> -        miniflow_assert_in_map(MF, OFS / 8);                            \
> -        *((uint16_t *)MF.data + 3) = VALUE;                             \
> -        MF.data++;                                                      \
> -    }                                                                   \
> -}
> -
> -#define miniflow_pad_to_64_(MF, OFS)                                    \
> -{                                                                       \
> -    MINIFLOW_ASSERT((OFS) % 8 != 0);                                    \
> -    miniflow_assert_in_map(MF, OFS / 8);                                \
> -                                                                        \
> -    memset((uint8_t *)MF.data + (OFS) % 8, 0, 8 - (OFS) % 8);           \
> -    MF.data++;                                                          \
> +#define miniflow_push_uint16_(MF, OFS, VALUE)   \
> +{                                               \
> +    MINIFLOW_ASSERT(MF.data < MF.end);          \
> +                                                \
> +    if ((OFS) % 8 == 0) {                       \
> +        miniflow_set_map(MF, OFS / 8);          \
> +        *(uint16_t *)MF.data = VALUE;           \
> +    } else if ((OFS) % 8 == 2) {                \
> +        miniflow_assert_in_map(MF, OFS / 8);    \
> +        *((uint16_t *)MF.data + 1) = VALUE;     \
> +    } else if ((OFS) % 8 == 4) {                \
> +        miniflow_assert_in_map(MF, OFS / 8);    \
> +        *((uint16_t *)MF.data + 2) = VALUE;     \
> +    } else if ((OFS) % 8 == 6) {                \
> +        miniflow_assert_in_map(MF, OFS / 8);    \
> +        *((uint16_t *)MF.data + 3) = VALUE;     \
> +        MF.data++;                              \
> +    }                                           \
> +}
> +
> +#define miniflow_pad_to_64_(MF, OFS)                            \
> +{                                                               \
> +    MINIFLOW_ASSERT((OFS) % 8 != 0);                            \
> +    miniflow_assert_in_map(MF, OFS / 8);                        \
> +                                                                \
> +    memset((uint8_t *)MF.data + (OFS) % 8, 0, 8 - (OFS) % 8);   \
> +    MF.data++;                                                  \
>  }
>
>  #define miniflow_push_be16_(MF, OFS, VALUE)                     \
>      miniflow_push_uint16_(MF, OFS, (OVS_FORCE uint16_t)VALUE);
>
> -#define miniflow_set_maps(MF, OFS, N_WORDS)                             \
> -{                                                                       \
> -    size_t ofs = (OFS);                                                 \
> -    size_t n_words = (N_WORDS);                                         \
> -    uint64_t n_words_mask = UINT64_MAX >> (64 - n_words);               \
> -                                                                        \
> -    MINIFLOW_ASSERT(n_words && MF.data + n_words <= MF.end);            \
> -    if (ofs < FLOW_TNL_U64S) {                                          \
> -        MINIFLOW_ASSERT(!(MF.maps.tnl_map & UINT64_MAX << ofs)          \
> -                        && !MF.maps.pkt_map);                           \
> -        MF.maps.tnl_map |= n_words_mask << ofs;                         \
> -        if (n_words > FLOW_TNL_U64S - ofs) {                            \
> -            MF.maps.pkt_map |= n_words_mask >> (FLOW_TNL_U64S - ofs);   \
> -        }                                                               \
> -    } else {                                                            \
> -        ofs -= FLOW_TNL_U64S;                                           \
> -        MINIFLOW_ASSERT(!(MF.maps.pkt_map & (UINT64_MAX << ofs)));      \
> -        MF.maps.pkt_map |= n_words_mask << ofs;                         \
> -    }                                                                   \
> +#define miniflow_set_maps(MF, OFS, N_WORDS)                     \
> +{                                                               \
> +    size_t ofs = (OFS);                                         \
> +    size_t n_words = (N_WORDS);                                 \
> +                                                                \
> +    MINIFLOW_ASSERT(n_words && MF.data + n_words <= MF.end);    \
> +    ASSERT_FLOWMAP_NOT_SET(&MF.map, ofs);                       \
> +    flowmap_set(&MF.map, ofs, n_words);                         \
>  }
>
>  /* Data at 'valuep' may be unaligned. */
> @@ -461,7 +440,8 @@ miniflow_extract(struct dp_packet *packet, struct miniflow *dst)
>      const void *data = dp_packet_data(packet);
>      size_t size = dp_packet_size(packet);
>      uint64_t *values = miniflow_values(dst);
> -    struct mf_ctx mf = { { 0, 0 }, values, values + FLOW_U64S };
> +    struct mf_ctx mf = { FLOWMAP_EMPTY_INITIALIZER, values,
> +                         values + FLOW_U64S };
>      const char *l2;
>      ovs_be16 dl_type;
>      uint8_t nw_frag, nw_tos, nw_ttl, nw_proto;
> @@ -767,7 +747,7 @@ miniflow_extract(struct dp_packet *packet, struct miniflow *dst)
>          }
>      }
>   out:
> -    *dst = mf.maps;
> +    dst->map = mf.map;
>  }
>
>  /* For every bit of a field that is wildcarded in 'wildcards', sets the
> @@ -1255,56 +1235,74 @@ void flow_wildcards_init_for_packet(struct flow_wildcards *wc,
>   *
>   * This is a less precise version of flow_wildcards_init_for_packet() above. */
>  void
> -flow_wc_map(const struct flow *flow, struct miniflow *map)
> +flow_wc_map(const struct flow *flow, struct flowmap *map)
>  {
>      /* Update this function whenever struct flow changes. */
>      BUILD_ASSERT_DECL(FLOW_WC_SEQ == 33);
>
> -    map->tnl_map = 0;
> +    flowmap_init(map);
> +
>      if (flow->tunnel.ip_dst) {
> -        map->tnl_map = MINIFLOW_TNL_MAP(tunnel);
> +        FLOWMAP_SET(map, tunnel);
>          if (!flow->tunnel.metadata.opt_map) {
> -            map->tnl_map &= ~MINIFLOW_TNL_MAP(tunnel.metadata);
> +            FLOWMAP_CLEAR(map, tunnel.metadata);
>          }
>      }
>
>      /* Metadata fields that can appear on packet input. */
> -    map->pkt_map = MINIFLOW_PKT_MAP(skb_priority) | MINIFLOW_PKT_MAP(pkt_mark)
> -        | MINIFLOW_PKT_MAP(recirc_id) | MINIFLOW_PKT_MAP(dp_hash)
> -        | MINIFLOW_PKT_MAP(in_port)
> -        | MINIFLOW_PKT_MAP(dl_dst) | MINIFLOW_PKT_MAP(dl_src)
> -        | MINIFLOW_PKT_MAP(dl_type) | MINIFLOW_PKT_MAP(vlan_tci);
> +    FLOWMAP_SET(map, skb_priority);
> +    FLOWMAP_SET(map, pkt_mark);
> +    FLOWMAP_SET(map, recirc_id);
> +    FLOWMAP_SET(map, dp_hash);
> +    FLOWMAP_SET(map, in_port);
> +    FLOWMAP_SET(map, dl_dst);
> +    FLOWMAP_SET(map, dl_src);
> +    FLOWMAP_SET(map, dl_type);
> +    FLOWMAP_SET(map, vlan_tci);
>
>      /* Ethertype-dependent fields. */
>      if (OVS_LIKELY(flow->dl_type == htons(ETH_TYPE_IP))) {
> -        map->pkt_map |= MINIFLOW_PKT_MAP(nw_src) | MINIFLOW_PKT_MAP(nw_dst)
> -            | MINIFLOW_PKT_MAP(nw_proto) | MINIFLOW_PKT_MAP(nw_frag)
> -            | MINIFLOW_PKT_MAP(nw_tos) | MINIFLOW_PKT_MAP(nw_ttl);
> +        FLOWMAP_SET(map, nw_src);
> +        FLOWMAP_SET(map, nw_dst);
> +        FLOWMAP_SET(map, nw_proto);
> +        FLOWMAP_SET(map, nw_frag);
> +        FLOWMAP_SET(map, nw_tos);
> +        FLOWMAP_SET(map, nw_ttl);
> +
>          if (OVS_UNLIKELY(flow->nw_proto == IPPROTO_IGMP)) {
> -            map->pkt_map |= MINIFLOW_PKT_MAP(igmp_group_ip4);
> +            FLOWMAP_SET(map, igmp_group_ip4);
>          } else {
> -            map->pkt_map |= MINIFLOW_PKT_MAP(tcp_flags)
> -                | MINIFLOW_PKT_MAP(tp_src) | MINIFLOW_PKT_MAP(tp_dst);
> +            FLOWMAP_SET(map, tcp_flags);
> +            FLOWMAP_SET(map, tp_src);
> +            FLOWMAP_SET(map, tp_dst);
>          }
>      } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
> -        map->pkt_map |= MINIFLOW_PKT_MAP(ipv6_src) | MINIFLOW_PKT_MAP(ipv6_dst)
> -            | MINIFLOW_PKT_MAP(ipv6_label)
> -            | MINIFLOW_PKT_MAP(nw_proto) | MINIFLOW_PKT_MAP(nw_frag)
> -            | MINIFLOW_PKT_MAP(nw_tos) | MINIFLOW_PKT_MAP(nw_ttl);
> +        FLOWMAP_SET(map, ipv6_src);
> +        FLOWMAP_SET(map, ipv6_dst);
> +        FLOWMAP_SET(map, ipv6_label);
> +        FLOWMAP_SET(map, nw_proto);
> +        FLOWMAP_SET(map, nw_frag);
> +        FLOWMAP_SET(map, nw_tos);
> +        FLOWMAP_SET(map, nw_ttl);
> +
>          if (OVS_UNLIKELY(flow->nw_proto == IPPROTO_ICMPV6)) {
> -            map->pkt_map |= MINIFLOW_PKT_MAP(nd_target)
> -                | MINIFLOW_PKT_MAP(arp_sha) | MINIFLOW_PKT_MAP(arp_tha);
> +            FLOWMAP_SET(map, nd_target);
> +            FLOWMAP_SET(map, arp_sha);
> +            FLOWMAP_SET(map, arp_tha);
>          } else {
> -            map->pkt_map |= MINIFLOW_PKT_MAP(tcp_flags)
> -                | MINIFLOW_PKT_MAP(tp_src) | MINIFLOW_PKT_MAP(tp_dst);
> +            FLOWMAP_SET(map, tcp_flags);
> +            FLOWMAP_SET(map, tp_src);
> +            FLOWMAP_SET(map, tp_dst);
>          }
>      } else if (eth_type_mpls(flow->dl_type)) {
> -        map->pkt_map |= MINIFLOW_PKT_MAP(mpls_lse);
> +        FLOWMAP_SET(map, mpls_lse);
>      } else if (flow->dl_type == htons(ETH_TYPE_ARP) ||
>                 flow->dl_type == htons(ETH_TYPE_RARP)) {
> -        map->pkt_map |= MINIFLOW_PKT_MAP(nw_src) | MINIFLOW_PKT_MAP(nw_dst)
> -            | MINIFLOW_PKT_MAP(nw_proto)
> -            | MINIFLOW_PKT_MAP(arp_sha) | MINIFLOW_PKT_MAP(arp_tha);
> +        FLOWMAP_SET(map, nw_src);
> +        FLOWMAP_SET(map, nw_dst);
> +        FLOWMAP_SET(map, nw_proto);
> +        FLOWMAP_SET(map, arp_sha);
> +        FLOWMAP_SET(map, arp_tha);
>      }
>  }
>
> @@ -1458,11 +1456,14 @@ miniflow_hash_5tuple(const struct miniflow *flow, uint32_t basis)
>
>          /* Separate loops for better optimization. */
>          if (dl_type == htons(ETH_TYPE_IPV6)) {
> -            struct miniflow maps = { 0, MINIFLOW_PKT_MAP(ipv6_src)
> -                                     | MINIFLOW_PKT_MAP(ipv6_dst) };
> +            struct flowmap map;
>              uint64_t value;
>
> -            MINIFLOW_FOR_EACH_IN_PKT_MAP(value, flow, maps) {
> +            flowmap_init(&map);
> +            FLOWMAP_SET(&map, ipv6_src);
> +            FLOWMAP_SET(&map, ipv6_dst);
> +
> +            MINIFLOW_FOR_EACH_IN_FLOWMAP(value, flow, map) {
>                  hash = hash_add64(hash, value);
>              }
>          } else {
> @@ -2212,9 +2213,8 @@ flow_compose(struct dp_packet *p, const struct flow *flow)
>  /* Compressed flow. */
>
>  /* Completes an initialization of 'dst' as a miniflow copy of 'src' begun by
> - * the caller.  The caller must have already computed 'dst->tnl_map' and
> - * 'dst->pkt_map' properly to indicate the significant uint64_t elements of
> - * 'src'.
> + * the caller.  The caller must have already computed 'dst->map' properly to
> + * indicate the significant uint64_t elements of 'src'.
>   *
>   * 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,
> @@ -2222,12 +2222,11 @@ flow_compose(struct dp_packet *p, const struct flow *flow)
>  void
>  miniflow_init(struct miniflow *dst, const struct flow *src)
>  {
> -    const uint64_t *src_u64 = (const uint64_t *) src;
>      uint64_t *dst_u64 = miniflow_values(dst);
>      size_t idx;
>
> -    MAPS_FOR_EACH_INDEX(idx, *dst) {
> -        *dst_u64++ = src_u64[idx];
> +    FLOWMAP_FOR_EACH_INDEX(idx, dst->map) {
> +        *dst_u64++ = flow_u64_value(src, idx);
>      }
>  }
>
> @@ -2235,21 +2234,11 @@ miniflow_init(struct miniflow *dst, const struct flow *src)
>  void
>  miniflow_map_init(struct miniflow *flow, const struct flow *src)
>  {
> -    const uint64_t *src_u64 = (const uint64_t *) src;
> -    int i;
> -
>      /* Initialize map, counting the number of nonzero elements. */
> -    flow->tnl_map = 0;
> -    for (i = 0; i < FLOW_TNL_U64S; i++) {
> -        if (src_u64[i]) {
> -            flow->tnl_map |= UINT64_C(1) << i;
> -        }
> -    }
> -    src_u64 += FLOW_TNL_U64S;
> -    flow->pkt_map = 0;
> -    for (i = 0; i < FLOW_U64S - FLOW_TNL_U64S; i++) {
> -        if (src_u64[i]) {
> -            flow->pkt_map |= UINT64_C(1) << i;
> +    flowmap_init(&flow->map);
> +    for (size_t i = 0; i < FLOW_U64S; i++) {
> +        if (flow_u64_value(src, i)) {
> +            flowmap_set(&flow->map, i, 1);
>          }
>      }
>  }
> @@ -2317,26 +2306,16 @@ miniflow_equal(const struct miniflow *a, const struct miniflow *b)
>      const uint64_t *ap = miniflow_get_values(a);
>      const uint64_t *bp = miniflow_get_values(b);
>
> -    if (OVS_LIKELY(miniflow_equal_maps(a, b))) {
> +    /* This is mostly called after a matching hash, so it is highly likely that
> +     * the maps are equal as well. */
> +    if (OVS_LIKELY(flowmap_equal(a->map, b->map))) {
>          return !memcmp(ap, bp, miniflow_n_values(a) * sizeof *ap);
>      } else {
> -        uint64_t map;
> -
> -        map = a->tnl_map | b->tnl_map;
> -        for (; map; map = zero_rightmost_1bit(map)) {
> -            uint64_t bit = rightmost_1bit(map);
> -
> -            if ((a->tnl_map & bit ? *ap++ : 0)
> -                != (b->tnl_map & bit ? *bp++ : 0)) {
> -                return false;
> -            }
> -        }
> -        map = a->pkt_map | b->pkt_map;
> -        for (; map; map = zero_rightmost_1bit(map)) {
> -            uint64_t bit = rightmost_1bit(map);
> +        size_t idx;
>
> -            if ((a->pkt_map & bit ? *ap++ : 0)
> -                != (b->pkt_map & bit ? *bp++ : 0)) {
> +        FLOWMAP_FOR_EACH_INDEX (idx, flowmap_or(a->map, b->map)) {
> +            if ((FLOWMAP_IS_SET(a->map, idx) ? *ap++ : 0)
> +                != (FLOWMAP_IS_SET(b->map, idx) ? *bp++ : 0)) {
>                  return false;
>              }
>          }
> @@ -2354,7 +2333,7 @@ miniflow_equal_in_minimask(const struct miniflow *a, const struct miniflow *b,
>      const uint64_t *p = miniflow_get_values(&mask->masks);
>      size_t idx;
>
> -    MAPS_FOR_EACH_INDEX(idx, mask->masks) {
> +    FLOWMAP_FOR_EACH_INDEX(idx, mask->masks.map) {
>          if ((miniflow_get(a, idx) ^ miniflow_get(b, idx)) & *p++) {
>              return false;
>          }
> @@ -2369,12 +2348,11 @@ bool
>  miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow *b,
>                                  const struct minimask *mask)
>  {
> -    const uint64_t *b_u64 = (const uint64_t *) b;
>      const uint64_t *p = miniflow_get_values(&mask->masks);
>      size_t idx;
>
> -    MAPS_FOR_EACH_INDEX(idx, mask->masks) {
> -        if ((miniflow_get(a, idx) ^ b_u64[idx]) & *p++) {
> +    FLOWMAP_FOR_EACH_INDEX(idx, mask->masks.map) {
> +        if ((miniflow_get(a, idx) ^ flow_u64_value(b, idx)) & *p++) {
>              return false;
>          }
>      }
> @@ -2411,31 +2389,16 @@ minimask_combine(struct minimask *dst_,
>      uint64_t *dst_values = storage;
>      const struct miniflow *a = &a_->masks;
>      const struct miniflow *b = &b_->masks;
> -    const uint64_t *ap = miniflow_get_values(a);
> -    const uint64_t *bp = miniflow_get_values(b);
>      size_t idx;
>
> -    dst->tnl_map = 0;
> -    MAP_FOR_EACH_INDEX(idx, a->tnl_map & b->tnl_map) {
> -        /* Both 'a' and 'b' have non-zero data at 'idx'. */
> -        uint64_t mask = *miniflow_values_get__(ap, a->tnl_map, idx)
> -            & *miniflow_values_get__(bp, b->tnl_map, idx);
> +    flowmap_init(&dst->map);
>
> -        if (mask) {
> -            dst->tnl_map |= UINT64_C(1) << idx;
> -            *dst_values++ = mask;
> -        }
> -    }
> -    dst->pkt_map = 0;
> -    ap += count_1bits(a->tnl_map);   /* Skip tnl_map values. */
> -    bp += count_1bits(b->tnl_map);   /* Skip tnl_map values. */
> -    MAP_FOR_EACH_INDEX(idx, a->pkt_map & b->pkt_map) {
> +    FLOWMAP_FOR_EACH_INDEX(idx, flowmap_and(a->map, b->map)) {
>          /* Both 'a' and 'b' have non-zero data at 'idx'. */
> -        uint64_t mask = *miniflow_values_get__(ap, a->pkt_map, idx)
> -            & *miniflow_values_get__(bp, b->pkt_map, idx);
> +        uint64_t mask = *miniflow_get__(a, idx) & *miniflow_get__(b, idx);
>
>          if (mask) {
> -            dst->pkt_map |= UINT64_C(1) << idx;
> +            flowmap_set(&dst->map, idx, 1);
>              *dst_values++ = mask;
>          }
>      }
> @@ -2454,10 +2417,8 @@ minimask_expand(const struct minimask *mask, struct flow_wildcards *wc)
>  bool
>  minimask_equal(const struct minimask *a, const struct minimask *b)
>  {
> -    return a->masks.tnl_map == b->masks.tnl_map
> -        && a->masks.pkt_map == b->masks.pkt_map &&
> -        !memcmp(miniflow_get_values(&a->masks), miniflow_get_values(&b->masks),
> -                MINIFLOW_VALUES_SIZE(miniflow_n_values(&a->masks)));
> +    return !memcmp(a, b, sizeof *a
> +                   + MINIFLOW_VALUES_SIZE(miniflow_n_values(&a->masks)));
>  }
>
>  /* Returns true if at least one bit matched by 'b' is wildcarded by 'a',
> @@ -2465,28 +2426,16 @@ minimask_equal(const struct minimask *a, const struct minimask *b)
>  bool
>  minimask_has_extra(const struct minimask *a, const struct minimask *b)
>  {
> -    const uint64_t *ap = miniflow_get_values(&a->masks);
>      const uint64_t *bp = miniflow_get_values(&b->masks);
>      size_t idx;
>
> -    MAP_FOR_EACH_INDEX(idx, b->masks.tnl_map) {
> +    FLOWMAP_FOR_EACH_INDEX(idx, b->masks.map) {
>          uint64_t b_u64 = *bp++;
>
>          /* 'b_u64' is non-zero, check if the data in 'a' is either zero
>           * or misses some of the bits in 'b_u64'. */
> -        if (!(a->masks.tnl_map & (UINT64_C(1) << idx))
> -            || ((*miniflow_values_get__(ap, a->masks.tnl_map, idx) & b_u64)
> -                != b_u64)) {
> -            return true; /* 'a' wildcards some bits 'b' doesn't. */
> -        }
> -    }
> -    ap += count_1bits(a->masks.tnl_map);   /* Skip tnl_map values. */
> -    MAP_FOR_EACH_INDEX(idx, b->masks.pkt_map) {
> -        uint64_t b_u64 = *bp++;
> -
> -        if (!(a->masks.pkt_map & (UINT64_C(1) << idx))
> -            || ((*miniflow_values_get__(ap, a->masks.pkt_map, idx) & b_u64)
> -                != b_u64)) {
> +        if (!MINIFLOW_IN_MAP(&a->masks, idx)
> +            || ((*miniflow_get__(&a->masks, idx) & b_u64) != b_u64)) {
>              return true; /* 'a' wildcards some bits 'b' doesn't. */
>          }
>      }
> diff --git a/lib/flow.h b/lib/flow.h
> index 17745ad..ab39060 100644
> --- a/lib/flow.h
> +++ b/lib/flow.h
> @@ -21,6 +21,7 @@
>  #include <stdbool.h>
>  #include <stdint.h>
>  #include <string.h>
> +#include "bitmap.h"
>  #include "byte-order.h"
>  #include "openflow/nicira-ext.h"
>  #include "openflow/openflow.h"
> @@ -150,8 +151,6 @@ struct flow {
>  };
>  BUILD_ASSERT_DECL(sizeof(struct flow) % sizeof(uint64_t) == 0);
>  BUILD_ASSERT_DECL(sizeof(struct flow_tnl) % sizeof(uint64_t) == 0);
> -/* Number of uint64_t units in flow tunnel metadata. */
> -#define FLOW_TNL_U64S (sizeof(struct flow_tnl) / sizeof(uint64_t))
>
>  #define FLOW_U64S (sizeof(struct flow) / sizeof(uint64_t))
>
> @@ -192,6 +191,14 @@ BUILD_ASSERT_DECL(FLOW_SEGMENT_3_ENDS_AT < sizeof(struct flow));
>
>  extern const uint8_t flow_segment_u64s[];
>
> +#define FLOW_U64_OFFSET(FIELD) offsetof(struct flow, FIELD) / sizeof(uint64_t)
> +#define FLOW_U64_OFFREM(FIELD) offsetof(struct flow, FIELD) % sizeof(uint64_t)
> +
> +/* Number of 64-bit units spanned by a 'FIELD'. */
> +#define FLOW_U64_SIZE(FIELD)                                            \
> +    DIV_ROUND_UP((FLOW_U64_OFFREM(FIELD) + sizeof(((struct flow *)0)->FIELD)), \
> +                 sizeof(uint64_t))
> +
>  void flow_extract(struct dp_packet *, struct flow *);
>
>  void flow_zero_wildcards(struct flow *, const struct flow_wildcards *);
> @@ -374,13 +381,214 @@ uint32_t flow_hash_in_wildcards(const struct flow *,
>  bool flow_equal_except(const struct flow *a, const struct flow *b,
>                         const struct flow_wildcards *);
>
> -/* Compressed flow. */
> +/* Bitmap for flow values.  For each 1-bit the corresponding flow value is
> + * explicitly specified, other values are zeroes.
> + *
> + * map_t must be wide enough to hold any member of struct flow. */
> +typedef unsigned long long map_t;
> +#define MAP_T_BITS (sizeof(map_t) * CHAR_BIT)
> +#define MAP_1 (map_t)1
> +#define MAP_MAX ULLONG_MAX
> +
> +#define MAP_IS_SET(MAP, IDX) ((MAP) & (MAP_1 << (IDX)))
> +
> +/* Iterate through the indices of all 1-bits in 'MAP'. */
> +#define MAP_FOR_EACH_INDEX(IDX, MAP)            \
> +    ULLONG_FOR_EACH_1(IDX, MAP)
> +
> +#define FLOWMAP_UNITS DIV_ROUND_UP(FLOW_U64S, MAP_T_BITS)
> +
> +struct flowmap {
> +    map_t bits[FLOWMAP_UNITS];
> +};
> +
> +#define FLOWMAP_EMPTY_INITIALIZER { { 0 } }
> +
> +static inline void flowmap_init(struct flowmap *);
> +static inline bool flowmap_equal(struct flowmap, struct flowmap);
> +static inline void flowmap_set(struct flowmap *, size_t ofs, size_t n_bits);
> +static inline void flowmap_clear(struct flowmap *, size_t ofs, size_t n_bits);
> +static inline struct flowmap flowmap_or(struct flowmap, struct flowmap);
> +static inline struct flowmap flowmap_and(struct flowmap, struct flowmap);
> +static inline bool flowmap_is_empty(struct flowmap);
> +static inline size_t flowmap_n_1bits(struct flowmap);
> +
> +#define FLOWMAP_IS_SET(FM, IDX)                                     \
> +    MAP_IS_SET((FM).bits[(IDX) / MAP_T_BITS], (IDX) % MAP_T_BITS)
> +
> +/* XXX: Assumes 'SIZE' does not span units!. */
> +#define FLOWMAP_ARE_SET(FM, IDX, SIZE)                              \
> +    ((FM)->bits[(IDX) / MAP_T_BITS] &                               \
> +     (((MAP_1 << (SIZE)) - 1) << ((IDX) % MAP_T_BITS)))
> +
> +#define FLOWMAP_HAS_FIELD(FM, FIELD)                                    \
> +    FLOWMAP_ARE_SET(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
> +
> +#define FLOWMAP_SET(FM, FIELD)                                      \
> +    flowmap_set(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
> +
> +/* XXX: Only works for full 64-bit units. */
> +#define FLOWMAP_CLEAR(FM, FIELD)                                        \
> +    BUILD_ASSERT_DECL(FLOW_U64_OFFREM(FIELD) == 0);                     \
> +    BUILD_ASSERT_DECL(sizeof(((struct flow *)0)->FIELD) % sizeof(uint64_t) == 0); \
> +    flowmap_clear(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
> +
> +/* Iterate through all units in 'FMAP'. */
> +#define FLOWMAP_FOR_EACH_UNIT(UNIT)                     \
> +    for ((UNIT) = 0; (UNIT) < FLOWMAP_UNITS; (UNIT)++)
> +
> +/* Iterate through all map units in 'FMAP'. */
> +#define FLOWMAP_FOR_EACH_MAP(MAP, FLOWMAP)                              \
> +    for (size_t unit__ = 0;                                             \
> +         unit__ < FLOWMAP_UNITS && ((MAP) = (FLOWMAP).bits[unit__], true); \
> +         unit__++)
> +
> +struct flowmap_aux;
> +static inline bool flowmap_next_index(struct flowmap_aux *, size_t *idx);
> +static inline struct flowmap_aux flowmap_aux_initializer(const struct flowmap);
> +
> +/* Iterate through all struct flow u64 indices specified by 'MAP'.  This is a
> + * slower but easier version of the FLOWMAP_FOR_EACH_MAP() &
> + * MAP_FOR_EACH_INDEX() combination. */
> +#define FLOWMAP_FOR_EACH_INDEX(IDX, MAP)                            \
> +    for (struct flowmap_aux aux__ = flowmap_aux_initializer(MAP);   \
> +         flowmap_next_index(&aux__, &(IDX));)
> +
> +
> +/* Flowmap inline implementations. */
> +static inline void
> +flowmap_init(struct flowmap *fm)
> +{
> +    memset(fm, 0, sizeof *fm);
> +}
> +
> +static inline bool
> +flowmap_equal(struct flowmap a, struct flowmap b)
> +{
> +    return !memcmp(&a, &b, sizeof a);
> +}
>
> -/* Check that all tunnel fields fit into a single map. */
> -BUILD_ASSERT_DECL(FLOW_TNL_U64S <= 64);
> +/* Set the 'n_bits' consecutive bits in 'fm', starting at bit 'ofs'.
> + * 'n_bits' can be at most the number of 64-bit units in the widest member
> + * of struct flow. */
> +static inline void
> +flowmap_set(struct flowmap *fm, size_t ofs, size_t n_bits)
> +{
> +    map_t n_bits_mask = MAP_MAX >> (MAP_T_BITS - n_bits);
> +    size_t unit = ofs / MAP_T_BITS;
> +
> +    ofs %= MAP_T_BITS;
> +
> +    fm->bits[unit] |= n_bits_mask << ofs;
> +    if (unit + 1 < FLOWMAP_UNITS && ofs + n_bits > MAP_T_BITS) {
> +        /* 'MAP_T_BITS - ofs' bits were set on 'unit', set the remaining
> +         * bits from the next unit. */
> +        fm->bits[unit + 1] |= n_bits_mask >> (MAP_T_BITS - ofs);
> +    }
> +}
> +
> +/* Clears the 'n_bits' consecutive bits in 'fm', starting at bit 'ofs'.
> + * 'n_bits' can be at most the number of 64-bit units in the widest member
> + * of struct flow. */
> +static inline void
> +flowmap_clear(struct flowmap *fm, size_t ofs, size_t n_bits)
> +{
> +    map_t n_bits_mask = MAP_MAX >> (MAP_T_BITS - n_bits);
> +    size_t unit = ofs / MAP_T_BITS;
> +
> +    ofs %= MAP_T_BITS;
> +
> +    fm->bits[unit] &= ~(n_bits_mask << ofs);
> +    if (unit + 1 < FLOWMAP_UNITS && ofs + n_bits > MAP_T_BITS) {
> +        /* 'MAP_T_BITS - ofs' bits were cleared on 'unit', clear the
> +         * remaining bits from the next unit. */
> +        fm->bits[unit + 1] &= ~(n_bits_mask >> (MAP_T_BITS - ofs));
> +    }
> +}
> +
> +/* OR the bits in the flowmaps. */
> +static inline struct flowmap
> +flowmap_or(struct flowmap a, const struct flowmap b)
> +{
> +    struct flowmap map;
> +    size_t unit;
>
> -/* Check that all non-tunnel fields fit into a single map. */
> -BUILD_ASSERT_DECL(FLOW_U64S - FLOW_TNL_U64S <= 64);
> +    FLOWMAP_FOR_EACH_UNIT (unit) {
> +        map.bits[unit] = a.bits[unit] | b.bits[unit];
> +    }
> +    return map;
> +}
> +
> +/* AND the bits in the flowmaps. */
> +static inline struct flowmap
> +flowmap_and(struct flowmap a, const struct flowmap b)
> +{
> +    struct flowmap map;
> +    size_t unit;
> +
> +    FLOWMAP_FOR_EACH_UNIT (unit) {
> +        map.bits[unit] = a.bits[unit] & b.bits[unit];
> +    }
> +    return map;
> +}
> +
> +static inline bool
> +flowmap_is_empty(const struct flowmap fm)
> +{
> +    map_t map;
> +
> +    FLOWMAP_FOR_EACH_MAP (map, fm) {
> +        if (map) {
> +            return false;
> +        }
> +    }
> +    return true;
> +}
> +
> +static inline size_t
> +flowmap_n_1bits(struct flowmap fm)
> +{
> +    size_t unit, n_1bits = 0;
> +
> +    FLOWMAP_FOR_EACH_UNIT (unit) {
> +        n_1bits += count_1bits(fm.bits[unit]);
> +    }
> +    return n_1bits;
> +}
> +
> +struct flowmap_aux {
> +    size_t unit;
> +    struct flowmap map;
> +};
> +
> +static inline struct flowmap_aux
> +flowmap_aux_initializer(const struct flowmap fm)
> +{
> +    struct flowmap_aux aux;
> +
> +    aux.unit = 0;
> +    aux.map = fm;
> +
> +    return aux;
> +}
> +
> +static inline bool
> +flowmap_next_index(struct flowmap_aux *aux, size_t *idx)
> +{
> +    map_t *map;
> +
> +    while (!*(map = &aux->map.bits[aux->unit])) {
> +        if (++aux->unit == FLOWMAP_UNITS) {
> +            return false;
> +        }
> +    }
> +    *idx = aux->unit * MAP_T_BITS + raw_ctz(*map);
> +    *map = zero_rightmost_1bit(*map);
> +    return true;
> +}
> +
> +
> +/* Compressed flow. */
>
>  /* A sparse representation of a "struct flow".
>   *
> @@ -389,14 +597,13 @@ BUILD_ASSERT_DECL(FLOW_U64S - FLOW_TNL_U64S <= 64);
>   * importantly, minimizes the number of accessed cache lines.  Second, it saves
>   * time when the goal is to iterate over only the nonzero parts of the struct.
>   *
> - * The map members hold one bit for each uint64_t in a "struct flow".  Each
> + * The map member hold one bit for each uint64_t in a "struct flow".  Each
>   * 0-bit indicates that the corresponding uint64_t is zero, each 1-bit that it
>   * *may* be nonzero (see below how this applies to minimasks).
>   *
> - * The values indicated by 'tnl_map' and 'pkt_map' always follow the miniflow
> - * in memory.  The user of the miniflow is responsible for always having enough
> - * storage after the struct miniflow corresponding to the number of 1-bits in
> - * maps.
> + * The values indicated by 'map' always follow the miniflow in memory.  The
> + * user of the miniflow is responsible for always having enough storage after
> + * the struct miniflow corresponding to the number of 1-bits in maps.
>   *
>   * Elements in values array are allowed to be zero.  This is useful for "struct
>   * minimatch", for which ensuring that the miniflow and minimask members have
> @@ -407,13 +614,12 @@ BUILD_ASSERT_DECL(FLOW_U64S - FLOW_TNL_U64S <= 64);
>   * A miniflow is always dynamically allocated so that the maps are followed by
>   * at least as many elements as there are 1-bits in maps. */
>  struct miniflow {
> -    uint64_t tnl_map;
> -    uint64_t pkt_map;
> +    struct flowmap map;
>      /* Followed by:
>       *     uint64_t values[n];
>       * where 'n' is miniflow_n_values(miniflow). */
>  };
> -BUILD_ASSERT_DECL(sizeof(struct miniflow) == 2 * sizeof(uint64_t));
> +BUILD_ASSERT_DECL(sizeof(struct miniflow) % sizeof(uint64_t) == 0);
>
>  #define MINIFLOW_VALUES_SIZE(COUNT) ((COUNT) * sizeof(uint64_t))
>
> @@ -434,7 +640,7 @@ struct pkt_metadata;
>   * were extracted. */
>  void miniflow_extract(struct dp_packet *packet, struct miniflow *dst);
>  void miniflow_map_init(struct miniflow *, const struct flow *);
> -void flow_wc_map(const struct flow *, struct miniflow *);
> +void flow_wc_map(const struct flow *, struct flowmap *);
>  size_t miniflow_alloc(struct miniflow *dsts[], size_t n,
>                        const struct miniflow *src);
>  void miniflow_init(struct miniflow *, const struct flow *);
> @@ -457,166 +663,127 @@ static inline uint64_t *flow_u64_lvalue(struct flow *flow, size_t index)
>  static inline size_t
>  miniflow_n_values(const struct miniflow *flow)
>  {
> -    return count_1bits(flow->tnl_map) + count_1bits(flow->pkt_map);
> +    return flowmap_n_1bits(flow->map);
>  }
>
>  struct flow_for_each_in_maps_aux {
> -    const uint64_t *values;
> -    struct miniflow maps;
> +    const struct flow *flow;
> +    struct flowmap_aux map_aux;
>  };
>
> -static inline uint64_t
> -flow_values_get_next_in_map(const uint64_t *values, uint64_t *map)
> -{
> -    uint64_t value = values[raw_ctz(*map)];
> -
> -    *map = zero_rightmost_1bit(*map);
> -
> -    return value;
> -}
> -
>  static inline bool
>  flow_values_get_next_in_maps(struct flow_for_each_in_maps_aux *aux,
>                               uint64_t *value)
>  {
> -    if (aux->maps.tnl_map) {
> -        *value = flow_values_get_next_in_map(aux->values, &aux->maps.tnl_map);
> -        return true;
> -    }
> -    if (aux->maps.pkt_map) {
> -        *value = flow_values_get_next_in_map(aux->values + FLOW_TNL_U64S,
> -                                             &aux->maps.pkt_map);
> +    size_t idx;
> +
> +    if (flowmap_next_index(&aux->map_aux, &idx)) {
> +        *value = flow_u64_value(aux->flow, idx);
>          return true;
>      }
>      return false;
>  }
>
> -/* Iterate through all flow tunnel u64 values specified by 'MAPS'. */
> +/* Iterate through all flow u64 values specified by 'MAPS'. */
>  #define FLOW_FOR_EACH_IN_MAPS(VALUE, FLOW, MAPS)            \
>      for (struct flow_for_each_in_maps_aux aux__             \
> -             = { (const uint64_t *)(FLOW), (MAPS) };        \
> +             = { (FLOW), flowmap_aux_initializer(MAPS) };   \
>           flow_values_get_next_in_maps(&aux__, &(VALUE));)
>
> -/* Iterate through all struct flow u64 indices specified by 'MAP'. */
> -#define MAP_FOR_EACH_INDEX(U64IDX, MAP)                 \
> -    for (uint64_t map__ = (MAP);                        \
> -         map__ && ((U64IDX) = raw_ctz(map__), true);    \
> -         map__ = zero_rightmost_1bit(map__))
> -
> -/* Iterate through all struct flow u64 indices specified by 'MAPS'. */
> -#define MAPS_FOR_EACH_INDEX(U64IDX, MAPS)                               \
> -    for (struct miniflow maps__ = (MAPS);                               \
> -         maps__.tnl_map                                                 \
> -             ? ((U64IDX) = raw_ctz(maps__.tnl_map),                     \
> -                maps__.tnl_map = zero_rightmost_1bit(maps__.tnl_map),   \
> -                true)                                                   \
> -             : (maps__.pkt_map &&                                       \
> -                ((U64IDX) = FLOW_TNL_U64S + raw_ctz(maps__.pkt_map),    \
> -                 maps__.pkt_map = zero_rightmost_1bit(maps__.pkt_map),  \
> -                 true));)
> -
> -#define FLOW_U64_SIZE(FIELD)                                            \
> -    DIV_ROUND_UP(sizeof(((struct flow *)0)->FIELD), sizeof(uint64_t))
> -
> -#define MINIFLOW_TNL_MAP(FIELD)                                         \
> -    (((UINT64_C(1) << FLOW_U64_SIZE(FIELD)) - 1)                        \
> -     << (offsetof(struct flow, FIELD) / sizeof(uint64_t)))
> -#define MINIFLOW_PKT_MAP(FIELD)                                         \
> -    (((UINT64_C(1) << FLOW_U64_SIZE(FIELD)) - 1)                        \
> -     << ((offsetof(struct flow, FIELD) / sizeof(uint64_t)) - FLOW_TNL_U64S))
> -
>  struct mf_for_each_in_map_aux {
> +    size_t unit;
> +    struct flowmap fmap;
> +    struct flowmap map;
>      const uint64_t *values;
> -    uint64_t fmap;
> -    uint64_t map;
>  };
>
>  static inline bool
>  mf_get_next_in_map(struct mf_for_each_in_map_aux *aux,
>                     uint64_t *value)
>  {
> -    if (aux->map) {
> -        uint64_t rm1bit = rightmost_1bit(aux->map);
> +    map_t *map, *fmap;
> +    map_t rm1bit;
>
> -        aux->map -= rm1bit;
> +    while (OVS_UNLIKELY(!*(map = &aux->map.bits[aux->unit]))) {
> +        /* Skip remaining data in the previous unit. */
> +        aux->values += count_1bits(aux->fmap.bits[aux->unit]);
> +        if (++aux->unit == FLOWMAP_UNITS) {
> +            return false;
> +        }
> +    }
>
> -        if (aux->fmap & rm1bit) {
> -            uint64_t trash = aux->fmap & (rm1bit - 1);
> +    rm1bit = rightmost_1bit(*map);
> +    *map -= rm1bit;
> +    fmap = &aux->fmap.bits[aux->unit];
>
> -            aux->fmap -= trash;
> -            /* count_1bits() is fast for systems where speed matters (e.g.,
> -             * DPDK), so we don't try avoid using it.
> -             * Advance 'aux->values' to point to the value for 'rm1bit'. */
> -            aux->values += count_1bits(trash);
> +    if (OVS_LIKELY(*fmap & rm1bit)) {
> +        map_t trash = *fmap & (rm1bit - 1);
>
> -            *value = *aux->values;
> -        } else {
> -            *value = 0;
> -        }
> -        return true;
> +        *fmap -= trash;
> +        /* count_1bits() is fast for systems where speed matters (e.g.,
> +         * DPDK), so we don't try avoid using it.
> +         * Advance 'aux->values' to point to the value for 'rm1bit'. */
> +        aux->values += count_1bits(trash);
> +
> +        *value = *aux->values;
> +    } else {
> +        *value = 0;
>      }
> -    return false;
> +    return true;
>  }
>
> -/* Iterate through miniflow TNL u64 values specified by 'MAPS'. */
> -#define MINIFLOW_FOR_EACH_IN_TNL_MAP(VALUE, FLOW, MAPS)                 \
> -    for (struct mf_for_each_in_map_aux aux__ =                          \
> -        { miniflow_get_values(FLOW), (FLOW)->tnl_map, (MAPS).tnl_map }; \
> -         mf_get_next_in_map(&aux__, &(VALUE));)
> -
> -/* Iterate through miniflow PKT u64 values specified by 'MAPS'. */
> -#define MINIFLOW_FOR_EACH_IN_PKT_MAP(VALUE, FLOW, MAPS)             \
> +/* Iterate through miniflow u64 values specified by 'FLOWMAP'. */
> +#define MINIFLOW_FOR_EACH_IN_FLOWMAP(VALUE, FLOW, FLOWMAP)          \
>      for (struct mf_for_each_in_map_aux aux__ =                      \
> -        { miniflow_get_values(FLOW) + count_1bits((FLOW)->tnl_map), \
> -                (FLOW)->pkt_map, (MAPS).pkt_map };                  \
> +        { 0, (FLOW)->map, (FLOWMAP), miniflow_get_values(FLOW) };   \
>           mf_get_next_in_map(&aux__, &(VALUE));)
>
> -/* This can be used when it is known that 'u64_idx' is set in 'map'. */
> +/* This can be used when it is known that 'idx' is set in 'map'. */
>  static inline const uint64_t *
> -miniflow_values_get__(const uint64_t *values, uint64_t map, size_t u64_idx)
> +miniflow_values_get__(const uint64_t *values, map_t map, size_t idx)
>  {
> -    return values + count_1bits(map & ((UINT64_C(1) << u64_idx) - 1));
> +    return values + count_1bits(map & ((MAP_1 << idx) - 1));
>  }
>
>  /* This can be used when it is known that 'u64_idx' is set in
>   * the map of 'mf'. */
>  static inline const uint64_t *
> -miniflow_get__(const struct miniflow *mf, size_t u64_idx)
> -{
> -    return OVS_LIKELY(u64_idx >= FLOW_TNL_U64S)
> -        ? miniflow_values_get__(miniflow_get_values(mf)
> -                                + count_1bits(mf->tnl_map),
> -                                mf->pkt_map, u64_idx - FLOW_TNL_U64S)
> -        : miniflow_values_get__(miniflow_get_values(mf), mf->tnl_map, u64_idx);
> -}
> -
> -#define MINIFLOW_IN_MAP(MF, U64_IDX)                                \
> -    (OVS_LIKELY(U64_IDX >= FLOW_TNL_U64S)                           \
> -     ? (MF)->pkt_map & (UINT64_C(1) << ((U64_IDX) - FLOW_TNL_U64S)) \
> -     : (MF)->tnl_map & (UINT64_C(1) << (U64_IDX)))
> -
> -/* Get the value of 'FIELD' of an up to 8 byte wide integer type 'TYPE' of
> - * a miniflow. */
> -#define MINIFLOW_GET_TYPE(MF, TYPE, OFS)                                \
> -    (MINIFLOW_IN_MAP(MF, (OFS) / sizeof(uint64_t))                      \
> -     ? ((OVS_FORCE const TYPE *)miniflow_get__(MF, (OFS) / sizeof(uint64_t))) \
> -     [(OFS) % sizeof(uint64_t) / sizeof(TYPE)]                          \
> +miniflow_get__(const struct miniflow *mf, size_t idx)
> +{
> +    const uint64_t *values = miniflow_get_values(mf);
> +    const map_t *map = mf->map.bits;
> +
> +    while (idx >= MAP_T_BITS) {
> +        idx -= MAP_T_BITS;
> +        values += count_1bits(*map++);
> +    }
> +    return miniflow_values_get__(values, *map, idx);
> +}
> +
> +#define MINIFLOW_IN_MAP(MF, IDX) FLOWMAP_IS_SET((MF)->map, IDX)
> +
> +/* Get the value of the struct flow 'FIELD' as up to 8 byte wide integer type
> + * 'TYPE' from miniflow 'MF'. */
> +#define MINIFLOW_GET_TYPE(MF, TYPE, FIELD)                              \
> +    (MINIFLOW_IN_MAP(MF, FLOW_U64_OFFSET(FIELD))                        \
> +     ? ((OVS_FORCE const TYPE *)miniflow_get__(MF, FLOW_U64_OFFSET(FIELD))) \
> +     [FLOW_U64_OFFREM(FIELD) / sizeof(TYPE)]                            \
>       : 0)
>
> -#define MINIFLOW_GET_U8(FLOW, FIELD)                                \
> -    MINIFLOW_GET_TYPE(FLOW, uint8_t, offsetof(struct flow, FIELD))
> -#define MINIFLOW_GET_U16(FLOW, FIELD)                               \
> -    MINIFLOW_GET_TYPE(FLOW, uint16_t, offsetof(struct flow, FIELD))
> -#define MINIFLOW_GET_BE16(FLOW, FIELD)                              \
> -    MINIFLOW_GET_TYPE(FLOW, ovs_be16, offsetof(struct flow, FIELD))
> -#define MINIFLOW_GET_U32(FLOW, FIELD)                               \
> -    MINIFLOW_GET_TYPE(FLOW, uint32_t, offsetof(struct flow, FIELD))
> -#define MINIFLOW_GET_BE32(FLOW, FIELD)                              \
> -    MINIFLOW_GET_TYPE(FLOW, ovs_be32, offsetof(struct flow, FIELD))
> -#define MINIFLOW_GET_U64(FLOW, FIELD)                               \
> -    MINIFLOW_GET_TYPE(FLOW, uint64_t, offsetof(struct flow, FIELD))
> -#define MINIFLOW_GET_BE64(FLOW, FIELD)                              \
> -    MINIFLOW_GET_TYPE(FLOW, ovs_be64, offsetof(struct flow, FIELD))
> +#define MINIFLOW_GET_U8(FLOW, FIELD)            \
> +    MINIFLOW_GET_TYPE(FLOW, uint8_t, FIELD)
> +#define MINIFLOW_GET_U16(FLOW, FIELD)           \
> +    MINIFLOW_GET_TYPE(FLOW, uint16_t, FIELD)
> +#define MINIFLOW_GET_BE16(FLOW, FIELD)          \
> +    MINIFLOW_GET_TYPE(FLOW, ovs_be16, FIELD)
> +#define MINIFLOW_GET_U32(FLOW, FIELD)           \
> +    MINIFLOW_GET_TYPE(FLOW, uint32_t, FIELD)
> +#define MINIFLOW_GET_BE32(FLOW, FIELD)          \
> +    MINIFLOW_GET_TYPE(FLOW, ovs_be32, FIELD)
> +#define MINIFLOW_GET_U64(FLOW, FIELD)           \
> +    MINIFLOW_GET_TYPE(FLOW, uint64_t, FIELD)
> +#define MINIFLOW_GET_BE64(FLOW, FIELD)          \
> +    MINIFLOW_GET_TYPE(FLOW, ovs_be64, FIELD)
>
>  static inline uint64_t miniflow_get(const struct miniflow *,
>                                      unsigned int u64_ofs);
> @@ -627,8 +794,6 @@ static inline ovs_be32 miniflow_get_be32(const struct miniflow *,
>  static inline uint16_t miniflow_get_vid(const struct miniflow *);
>  static inline uint16_t miniflow_get_tcp_flags(const struct miniflow *);
>  static inline ovs_be64 miniflow_get_metadata(const struct miniflow *);
> -static inline bool miniflow_equal_maps(const struct miniflow *a,
> -                                       const struct miniflow *b);
>
>  bool miniflow_equal(const struct miniflow *a, const struct miniflow *b);
>  bool miniflow_equal_in_minimask(const struct miniflow *a,
> @@ -679,7 +844,7 @@ minimask_is_catchall(const struct minimask *mask)
>      /* For every 1-bit in mask's map, the corresponding value is non-zero,
>       * so the only way the mask can not fix any bits or fields is for the
>       * map the be zero. */
> -    return mask->masks.tnl_map == 0 && mask->masks.pkt_map == 0;
> +    return flowmap_is_empty(mask->masks.map);
>  }
>
>  /* Returns the uint64_t that would be at byte offset '8 * u64_ofs' if 'flow'
> @@ -687,8 +852,7 @@ minimask_is_catchall(const struct minimask *mask)
>  static inline uint64_t miniflow_get(const struct miniflow *flow,
>                                      unsigned int u64_ofs)
>  {
> -    return MINIFLOW_IN_MAP(flow, u64_ofs)
> -        ? *miniflow_get__(flow, u64_ofs) : 0;
> +    return MINIFLOW_IN_MAP(flow, u64_ofs) ? *miniflow_get__(flow, u64_ofs) : 0;
>  }
>
>  static inline uint32_t miniflow_get_u32(const struct miniflow *flow,
> @@ -754,12 +918,6 @@ miniflow_get_metadata(const struct miniflow *flow)
>      return MINIFLOW_GET_BE64(flow, metadata);
>  }
>
> -static inline bool
> -miniflow_equal_maps(const struct miniflow *a, const struct miniflow *b)
> -{
> -    return a->tnl_map == b->tnl_map && a->pkt_map == b->pkt_map;
> -}
> -
>  /* Returns the mask for the OpenFlow 1.1+ "metadata" field in 'mask'.
>   *
>   * The return value is all-1-bits if 'mask' matches on the whole value of the
> @@ -781,11 +939,7 @@ flow_union_with_miniflow(struct flow *dst, const struct miniflow *src)
>      const uint64_t *p = miniflow_get_values(src);
>      size_t idx;
>
> -    MAP_FOR_EACH_INDEX(idx, src->tnl_map) {
> -        dst_u64[idx] |= *p++;
> -    }
> -    dst_u64 += FLOW_TNL_U64S;
> -    MAP_FOR_EACH_INDEX(idx, src->pkt_map) {
> +    FLOWMAP_FOR_EACH_INDEX(idx, src->map) {
>          dst_u64[idx] |= *p++;
>      }
>  }
> diff --git a/lib/match.c b/lib/match.c
> index 5175868..0177f82 100644
> --- a/lib/match.c
> +++ b/lib/match.c
> @@ -1256,13 +1256,12 @@ bool
>  minimatch_matches_flow(const struct minimatch *match,
>                         const struct flow *target)
>  {
> -    const uint64_t *target_u64 = (const uint64_t *) target;
>      const uint64_t *flowp = miniflow_get_values(match->flow);
>      const uint64_t *maskp = miniflow_get_values(&match->mask->masks);
>      size_t idx;
>
> -    MAPS_FOR_EACH_INDEX(idx, *match->flow) {
> -        if ((*flowp++ ^ target_u64[idx]) & *maskp++) {
> +    FLOWMAP_FOR_EACH_INDEX(idx, match->flow->map) {
> +        if ((*flowp++ ^ flow_u64_value(target, idx)) & *maskp++) {
>              return false;
>          }
>      }
> --
> 2.1.4
>



More information about the dev mailing list