[ovs-dev] [PATCH v2 3/9] miniflow: Use 64-bit map.

Jarno Rajahalme jrajahalme at nicira.com
Wed Nov 13 21:32:43 UTC 2013


Simplifies code a bit and makes it more understandable.  We are
currently at 44 or so uint32s, so there is room for extending struct
flow before we run out of bits in the map.

Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
 lib/flow.c  |  233 ++++++++++++++++++++++-------------------------------------
 lib/flow.h  |    5 +-
 lib/match.c |   13 +---
 3 files changed, 95 insertions(+), 156 deletions(-)

diff --git a/lib/flow.c b/lib/flow.c
index 8c336f6..137ce69 100644
--- 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..4ed2a41 100644
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -287,7 +287,8 @@ 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)
+/* #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 +322,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
--- 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;
-- 
1.7.10.4




More information about the dev mailing list