[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