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

[Alex Wang]

Thx a lot for the comments,

- Fixed the sparse warning,

- For the function usage, here is my judge:
"""
   The hsbm_complement and hsbm_intersect are the two most called
   function.
"""
   Actually, I spotted that hsbm_intersect can be made more efficient,


- Also thx for the stylistic suggestions, I need to learn to write cleaner
code~

Will send v2,

Thanks,
Alex Wang,

On Thu, May 28, 2015 at 3:19 PM, Ben Pfaff <blp at nicira.com> wrote:

> 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);
>
>