miniflow: Use 64-bit map.

Signed-off By: Jarno Rajahalme <jrajahalme@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>

diff --git a/lib/flow.c b/lib/flow.c
index 8c336f6..137ce69 100644 (file)
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -662,16 +662,11 @@ static void
 flow_union_with_miniflow(struct flow *dst, const struct miniflow *src)
 {
     uint32_t *dst_u32 = (uint32_t *) dst;
-    int ofs;
-    int i;
-
-    ofs = 0;
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t map;
+    int ofs = 0;
+    uint64_t map;
 
-        for (map = src->map[i]; map; map = zero_rightmost_1bit(map)) {
-            dst_u32[raw_ctz(map) + i * 32] |= src->values[ofs++];
-        }
+    for (map = src->map; map; map = zero_rightmost_1bit(map)) {
+        dst_u32[raw_ctz64(map)] |= src->values[ofs++];
     }
 }
 
@@ -1106,13 +1101,7 @@ flow_compose(struct ofpbuf *b, const struct flow *flow)
 static int
 miniflow_n_values(const struct miniflow *flow)
 {
-    int n, i;
-
-    n = 0;
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        n += popcount(flow->map[i]);
-    }
-    return n;
+    return popcount64(flow->map);
 }
 
 static uint32_t *
@@ -1139,16 +1128,12 @@ miniflow_init__(struct miniflow *dst, const struct flow *src, int n)
 {
     const uint32_t *src_u32 = (const uint32_t *) src;
     unsigned int ofs;
-    int i;
+    uint64_t map;
 
     dst->values = miniflow_alloc_values(dst, n);
     ofs = 0;
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t map;
-
-        for (map = dst->map[i]; map; map = zero_rightmost_1bit(map)) {
-            dst->values[ofs++] = src_u32[raw_ctz(map) + i * 32];
-        }
+    for (map = dst->map; map; map = zero_rightmost_1bit(map)) {
+        dst->values[ofs++] = src_u32[raw_ctz64(map)];
     }
 }
 
@@ -1163,10 +1148,11 @@ miniflow_init(struct miniflow *dst, const struct flow *src)
 
     /* Initialize dst->map, counting the number of nonzero elements. */
     n = 0;
-    memset(dst->map, 0, sizeof dst->map);
+    dst->map = 0;
+
     for (i = 0; i < FLOW_U32S; i++) {
         if (src_u32[i]) {
-            dst->map[i / 32] |= 1u << (i % 32);
+            dst->map |= UINT64_C(1) << i;
             n++;
         }
     }
@@ -1180,7 +1166,7 @@ void
 miniflow_init_with_minimask(struct miniflow *dst, const struct flow *src,
                             const struct minimask *mask)
 {
-    memcpy(dst->map, mask->masks.map, sizeof dst->map);
+    dst->map = mask->masks.map;
     miniflow_init__(dst, src, miniflow_n_values(dst));
 }
 
@@ -1190,7 +1176,7 @@ void
 miniflow_clone(struct miniflow *dst, const struct miniflow *src)
 {
     int n = miniflow_n_values(src);
-    memcpy(dst->map, src->map, sizeof dst->map);
+    dst->map = src->map;
     dst->values = miniflow_alloc_values(dst, n);
     memcpy(dst->values, src->values, n * sizeof *dst->values);
 }
@@ -1207,7 +1193,7 @@ miniflow_move(struct miniflow *dst, struct miniflow *src)
     } else {
         dst->values = src->values;
     }
-    memcpy(dst->map, src->map, sizeof dst->map);
+    dst->map = src->map;
 }
 
 /* Frees any memory owned by 'flow'.  Does not free the storage in which 'flow'
@@ -1231,21 +1217,12 @@ miniflow_expand(const struct miniflow *src, struct flow *dst)
 static const uint32_t *
 miniflow_get__(const struct miniflow *flow, unsigned int u32_ofs)
 {
-    if (!(flow->map[u32_ofs / 32] & (1u << (u32_ofs % 32)))) {
+    if (!(flow->map & (UINT64_C(1) << u32_ofs))) {
         static const uint32_t zero = 0;
         return &zero;
-    } else {
-        const uint32_t *p = flow->values;
-
-        BUILD_ASSERT(MINI_N_MAPS == 2);
-        if (u32_ofs < 32) {
-            p += popcount(flow->map[0] & ((1u << u32_ofs) - 1));
-        } else {
-            p += popcount(flow->map[0]);
-            p += popcount(flow->map[1] & ((1u << (u32_ofs - 32)) - 1));
-        }
-        return p;
     }
+    return flow->values
+        + popcount64(flow->map & ((UINT64_C(1) << u32_ofs) - 1));
 }
 
 /* Returns the uint32_t that would be at byte offset '4 * u32_ofs' if 'flow'
@@ -1281,28 +1258,24 @@ miniflow_equal(const struct miniflow *a, const struct miniflow *b)
 {
     const uint32_t *ap = a->values;
     const uint32_t *bp = b->values;
-    int i;
+    const uint64_t a_map = a->map;
+    const uint64_t b_map = b->map;
+    uint64_t map;
 
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        const uint32_t a_map = a->map[i];
-        const uint32_t b_map = b->map[i];
-        uint32_t map;
-
-        if (a_map == b_map) {
-            for (map = a_map; map; map = zero_rightmost_1bit(map)) {
-                if (*ap++ != *bp++) {
-                    return false;
-                }
+    if (a_map == b_map) {
+        for (map = a_map; map; map = zero_rightmost_1bit(map)) {
+            if (*ap++ != *bp++) {
+                return false;
             }
-        } else {
-            for (map = a_map | b_map; map; map = zero_rightmost_1bit(map)) {
-                uint32_t bit = rightmost_1bit(map);
-                uint32_t a_value = a_map & bit ? *ap++ : 0;
-                uint32_t b_value = b_map & bit ? *bp++ : 0;
+        }
+    } else {
+        for (map = a_map | b_map; map; map = zero_rightmost_1bit(map)) {
+            uint64_t bit = rightmost_1bit(map);
+            uint64_t a_value = a_map & bit ? *ap++ : 0;
+            uint64_t b_value = b_map & bit ? *bp++ : 0;
 
-                if (a_value != b_value) {
-                    return false;
-                }
+            if (a_value != b_value) {
+                return false;
             }
         }
     }
@@ -1317,20 +1290,17 @@ miniflow_equal_in_minimask(const struct miniflow *a, const struct miniflow *b,
                            const struct minimask *mask)
 {
     const uint32_t *p;
-    int i;
+    uint64_t map;
 
     p = mask->masks.values;
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t map;
 
-        for (map = mask->masks.map[i]; map; map = zero_rightmost_1bit(map)) {
-            int ofs = raw_ctz(map) + i * 32;
+    for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
+        int ofs = raw_ctz64(map);
 
-            if ((miniflow_get(a, ofs) ^ miniflow_get(b, ofs)) & *p) {
-                return false;
-            }
-            p++;
+        if ((miniflow_get(a, ofs) ^ miniflow_get(b, ofs)) & *p) {
+            return false;
         }
+        p++;
     }
 
     return true;
@@ -1344,20 +1314,17 @@ miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow *b,
 {
     const uint32_t *b_u32 = (const uint32_t *) b;
     const uint32_t *p;
-    int i;
+    uint64_t map;
 
     p = mask->masks.values;
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t map;
 
-        for (map = mask->masks.map[i]; map; map = zero_rightmost_1bit(map)) {
-            int ofs = raw_ctz(map) + i * 32;
+    for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
+        int ofs = raw_ctz64(map);
 
-            if ((miniflow_get(a, ofs) ^ b_u32[ofs]) & *p) {
-                return false;
-            }
-            p++;
+        if ((miniflow_get(a, ofs) ^ b_u32[ofs]) & *p) {
+            return false;
         }
+        p++;
     }
 
     return true;
@@ -1369,21 +1336,19 @@ miniflow_hash(const struct miniflow *flow, uint32_t basis)
 {
     const uint32_t *p = flow->values;
     uint32_t hash = basis;
-    int i;
-
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t hash_map = 0;
-        uint32_t map;
+    uint64_t hash_map = 0;
+    uint64_t map;
 
-        for (map = flow->map[i]; map; map = zero_rightmost_1bit(map)) {
-            if (*p) {
-                hash = mhash_add(hash, *p);
-                hash_map |= rightmost_1bit(map);
-            }
-            p++;
+    for (map = flow->map; map; map = zero_rightmost_1bit(map)) {
+        if (*p) {
+            hash = mhash_add(hash, *p);
+            hash_map |= rightmost_1bit(map);
         }
-        hash = mhash_add(hash, hash_map);
+        p++;
     }
+    hash = mhash_add(hash, hash_map);
+    hash = mhash_add(hash, hash_map >> 32);
+
     return mhash_finish(hash, p - flow->values);
 }
 
@@ -1398,19 +1363,16 @@ miniflow_hash_in_minimask(const struct miniflow *flow,
 {
     const uint32_t *p = mask->masks.values;
     uint32_t hash;
-    int i;
+    uint64_t map;
 
     hash = basis;
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t map;
 
-        for (map = mask->masks.map[i]; map; map = zero_rightmost_1bit(map)) {
-            if (*p) {
-                int ofs = raw_ctz(map) + i * 32;
-                hash = mhash_add(hash, miniflow_get(flow, ofs) & *p);
-            }
-            p++;
+    for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
+        if (*p) {
+            int ofs = raw_ctz64(map);
+            hash = mhash_add(hash, miniflow_get(flow, ofs) & *p);
         }
+        p++;
     }
 
     return mhash_finish(hash, (p - mask->masks.values) * 4);
@@ -1425,23 +1387,17 @@ uint32_t
 flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
                       uint32_t basis)
 {
-    const uint32_t *flow_u32;
+    const uint32_t *flow_u32 = (const uint32_t *)flow;
     const uint32_t *p = mask->masks.values;
     uint32_t hash;
-    int i;
+    uint64_t map;
 
     hash = basis;
-    flow_u32 = (const uint32_t *) flow;
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t map;
-
-        for (map = mask->masks.map[i]; map; map = zero_rightmost_1bit(map)) {
-            if (*p) {
-                hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p);
-            }
-            p++;
+    for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
+        if (*p) {
+            hash = mhash_add(hash, flow_u32[raw_ctz64(map)] & *p);
         }
-        flow_u32 += 32;
+        p++;
     }
 
     return mhash_finish(hash, (p - mask->masks.values) * 4);
@@ -1483,23 +1439,19 @@ minimask_combine(struct minimask *dst_,
     struct miniflow *dst = &dst_->masks;
     const struct miniflow *a = &a_->masks;
     const struct miniflow *b = &b_->masks;
-    int i, n;
+    uint64_t map;
+    int n = 0;
 
-    n = 0;
     dst->values = storage;
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t map;
-
-        dst->map[i] = 0;
-        for (map = a->map[i] & b->map[i]; map;
-             map = zero_rightmost_1bit(map)) {
-            int ofs = raw_ctz(map) + i * 32;
-            uint32_t mask = miniflow_get(a, ofs) & miniflow_get(b, ofs);
-
-            if (mask) {
-                dst->map[i] |= rightmost_1bit(map);
-                dst->values[n++] = mask;
-            }
+
+    dst->map = 0;
+    for (map = a->map & b->map; map; map = zero_rightmost_1bit(map)) {
+        int ofs = raw_ctz64(map);
+        uint32_t mask = miniflow_get(a, ofs) & miniflow_get(b, ofs);
+
+        if (mask) {
+            dst->map |= rightmost_1bit(map);
+            dst->values[n++] = mask;
         }
     }
 }
@@ -1556,20 +1508,15 @@ minimask_has_extra(const struct minimask *a_, const struct minimask *b_)
 {
     const struct miniflow *a = &a_->masks;
     const struct miniflow *b = &b_->masks;
-    int i;
-
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t map;
+    uint64_t map;
 
-        for (map = a->map[i] | b->map[i]; map;
-             map = zero_rightmost_1bit(map)) {
-            int ofs = raw_ctz(map) + i * 32;
-            uint32_t a_u32 = miniflow_get(a, ofs);
-            uint32_t b_u32 = miniflow_get(b, ofs);
+    for (map = a->map | b->map; map; map = zero_rightmost_1bit(map)) {
+        int ofs = raw_ctz64(map);
+        uint32_t a_u32 = miniflow_get(a, ofs);
+        uint32_t b_u32 = miniflow_get(b, ofs);
 
-            if ((a_u32 & b_u32) != b_u32) {
-                return true;
-            }
+        if ((a_u32 & b_u32) != b_u32) {
+            return true;
         }
     }
 
@@ -1583,15 +1530,11 @@ minimask_is_catchall(const struct minimask *mask_)
 {
     const struct miniflow *mask = &mask_->masks;
     const uint32_t *p = mask->values;
-    int i;
-
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t map;
+    uint64_t map;
 
-        for (map = mask->map[i]; map; map = zero_rightmost_1bit(map)) {
-            if (*p++) {
-                return false;
-            }
+    for (map = mask->map; map; map = zero_rightmost_1bit(map)) {
+        if (*p++) {
+            return false;
         }
     }
     return true;

diff --git a/lib/flow.h b/lib/flow.h
index 093d509..6fa3bbd 100644 (file)
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -287,7 +287,7 @@ bool flow_equal_except(const struct flow *a, const struct flow *b,
 /* Compressed flow. */
 
 #define MINI_N_INLINE (sizeof(void *) == 4 ? 7 : 8)
-#define MINI_N_MAPS DIV_ROUND_UP(FLOW_U32S, 32)
+BUILD_ASSERT_DECL(FLOW_U32S <= 64);
 
 /* A sparse representation of a "struct flow".
  *
@@ -321,9 +321,9 @@ bool flow_equal_except(const struct flow *a, const struct flow *b,
  * same 'map' allows optimization .
  */
 struct miniflow {
+    uint64_t map;
     uint32_t *values;
     uint32_t inline_values[MINI_N_INLINE];
-    uint32_t map[MINI_N_MAPS];
 };
 
 void miniflow_init(struct miniflow *, const struct flow *);

diff --git a/lib/match.c b/lib/match.c
index 0f674b0..35356c1 100644 (file)
--- a/lib/match.c
+++ b/lib/match.c
@@ -1173,17 +1173,12 @@ minimatch_matches_flow(const struct minimatch *match,
     const uint32_t *target_u32 = (const uint32_t *) target;
     const uint32_t *flowp = match->flow.values;
     const uint32_t *maskp = match->mask.masks.values;
-    int i;
-
-    for (i = 0; i < MINI_N_MAPS; i++) {
-        uint32_t map;
+    uint64_t map;
 
-        for (map = match->flow.map[i]; map; map = zero_rightmost_1bit(map)) {
-            if ((*flowp++ ^ target_u32[raw_ctz(map)]) & *maskp++) {
-                return false;
-            }
+    for (map = match->flow.map; map; map = zero_rightmost_1bit(map)) {
+        if ((*flowp++ ^ target_u32[raw_ctz64(map)]) & *maskp++) {
+            return false;
         }
-        target_u32 += 32;
     }
 
     return true;