[ovs-dev] [RFC HSA 2/4] hsa-match: Sparse representation of a byte array derived from "struct match".

Ben Pfaff blp at nicira.com
Thu May 28 22:19:03 UTC 2015


On Mon, Mar 30, 2015 at 03:46:27PM -0700, Alex Wang wrote:
> For conducting Header Space Analysis (HSA), we convert the wildcarded
> OpenFlow flow represented by 'struct match' into an encoded byte array.
> To further save memory, we use a sparse array to represent such byte
> array in the same way as 'struct miniflow'.  So, this commit implements
> the structs and functions for conversion between sparse array and
> 'struct match'.
> 
> This commit also implements the set operations (e.g. intersect, union,
> complementation and difference) as functions.
> 
> Signed-off-by: Alex Wang <alexw at nicira.com>

I also have a few stylistic suggestions that I'll present as an
incremental diff:

diff --git a/lib/hsa-match.c b/lib/hsa-match.c
index 3d69996..f337d2c 100644
--- a/lib/hsa-match.c
+++ b/lib/hsa-match.c
@@ -24,15 +24,15 @@
 void
 hsbm_init(struct hsbm *hsbm, const struct match *match)
 {
-    uint32_t *flow = (uint32_t *) &match->flow;
-    uint32_t *wc = (uint32_t *) &match->wc;
+    const uint32_t *flow = (const uint32_t *) &match->flow;
+    const uint32_t *wc = (const uint32_t *) &match->wc;
     size_t sz = 0;
     size_t i, j;
 
     hsbm->map = 0;
     hsbm->values = NULL;
 
-    /* Encodes every 4 bytes from 'match' to to 8 bytes and sets the
+    /* Encodes every 4 bytes from 'match' to 8 bytes and sets the
      * 'hsbm->map' and 'hsbm->values' correctly. */
     for (i = 0; i < HSBM_VALUES_MAX; i++) {
         uint64_t encoded_value = 0;
@@ -79,9 +79,7 @@ hsbm_init_one_bit(struct hsbm *hsbm, size_t map_idx, size_t bit_idx,
 void
 hsbm_uninit(struct hsbm *hsbm)
 {
-    if (hsbm->values) {
-        free(hsbm->values);
-    }
+    free(hsbm->values);
 }
 
 /* Destroys the 'hsbm'. */
@@ -114,21 +112,21 @@ hsbm_to_match(struct match *match, const struct hsbm *hsbm)
                 switch ((encoded_value >> (2*j)) & 0x3) {
                 /* wildcard unmasked (don't care), sets wc bit to '0'. */
                 case HSBM_VALUE_BIT_WC:
-                    wc_value = wc_value | ((uint32_t) 0x0 << j);
+                    wc_value |= (uint32_t) 0 << j;
                     break;
                 /* exact match '1'. */
                 case HSBM_VALUE_BIT_EM_ONE:
-                    flow_value = flow_value | ((uint32_t) 0x1 << j);
-                    wc_value = wc_value | ((uint32_t) 0x01 << j);
+                    flow_value |= (uint32_t) 1 << j;
+                    wc_value |= (uint32_t) 1 << j;
                     break;
                 /* exact match '0'. */
                 case HSBM_VALUE_BIT_EM_ZERO:
-                    flow_value = flow_value | ((uint32_t) 0x0 << j);
-                    wc_value = wc_value | ((uint32_t) 0x1 << j);
+                    flow_value |= (uint32_t) 0 << j;
+                    wc_value |= (uint32_t) 1 << j;
                     break;
                 /* no intersection, error! */
                 default:
-                    ovs_assert(false);
+                    OVS_NOT_REACHED();
                 }
             }
             flow[i] = flow_value;
@@ -147,8 +145,8 @@ hsbm_check_subset(const struct hsbm *hsbm1,
     size_t i;
 
     for (i = 0; i < HSBM_VALUES_MAX; i++) {
-        uint8_t bit1 = hsbm1->map >> i & 0x1;
-        uint8_t bit2 = hsbm2->map >> i & 0x1;
+        uint8_t bit1 = (hsbm1->map >> i) & 0x1;
+        uint8_t bit2 = (hsbm2->map >> i) & 0x1;
 
         if (bit1 == HSBM_MAP_BIT_WC && bit2 == HSBM_MAP_BIT_WC) {
             /* Do nothing. */
@@ -156,7 +154,7 @@ hsbm_check_subset(const struct hsbm *hsbm1,
             /* 'hsbm2' is more specific, 'hsbm1' cannot be its subset. */
             return false;
         } else if (bit1 == HSBM_MAP_BIT_NOT_WC && bit2 == HSBM_MAP_BIT_WC) {
-            /* 'hsbm1' is more specific, skips the exact value. */
+            /* 'hsbm1' is more specific, skip the exact value. */
             vals1++;
         } else {
             /* if both have specific values at index i, compares the values. */
@@ -227,7 +225,7 @@ hsbm_complement(struct hsbm *hsbm)
     size_t i;
 
     for (i = 0; i < HSBM_VALUES_MAX; i++) {
-        uint8_t map_bit = hsbm->map >> i & 0x1;
+        uint8_t map_bit = (hsbm->map >> i) & 0x1;
 
         if (map_bit == 0) {
             size_t j;
@@ -269,7 +267,7 @@ hsbm_intersect(struct hsbm *comp_1, struct hsbm *comp_2)
 
     result->map = comp_1->map & comp_2->map;
     for (i = 0; i < HSBM_VALUES_MAX; i++) {
-        if ((result->map >> i & 0x1) == 0) {
+        if (((result->map >> i) & 0x1) == 0) {
             n_vals++;
         }
     }
diff --git a/lib/hsa-match.h b/lib/hsa-match.h
index 63fabd4..0884765 100644
--- a/lib/hsa-match.h
+++ b/lib/hsa-match.h
@@ -63,7 +63,7 @@ struct hsbm {
 };
 
 /* Based on the description above, the maximum size of 'hsbm->values'
- * is the double of FLOW_U64S. */
+ * is twice FLOW_U64S. */
 #define HSBM_VALUES_MAX (FLOW_U64S * 2)
 BUILD_ASSERT_DECL(HSBM_VALUES_MAX < 64);
 



More information about the dev mailing list