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

Jarno Rajahalme jrajahalme at nicira.com
Wed Aug 5 17:53:46 UTC 2015


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