[ovs-dev] [PATCH v5 3/6] flow: Add struct flowmap.

Jarno Rajahalme jrajahalme at nicira.com
Wed Aug 26 23:05:38 UTC 2015


> On Aug 26, 2015, at 10:06 AM, Ben Pfaff <blp at nicira.com> wrote:
> 
> On Fri, Aug 21, 2015 at 03:25:20PM -0700, Jarno Rajahalme wrote:
>> Struct miniflow is now sometimes used just as a map.  Define a new
>> struct flowmap for that purpose.  The flowmap is defined as an array of
>> maps, and it is automatically sized according to the size of struct
>> flow, so it will be easier to maintain in the future.
>> 
>> It would have been tempting to use the existing struct bitmap for this
>> purpose. The main reason this is not feasible at the moment is that
>> some flowmap algorithms are simpler when it can be assumed that no
>> struct flow member requires more bits than can fit to a single map
>> unit. The tunnel member already requires more than 32 bits, so the map
>> unit needs to be 64 bits wide.
>> 
>> Performance critical algorithms enumerate the flowmap array units
>> explicitly, as it is easier for the compiler to optimize, compared to
>> the normal iterator.  Without this optimization a classifier lookup
>> without wildcard masks would be about 25% slower.
>> 
>> With this more general (and maintainable) algorithm the classifier
>> lookups are about 5% slower, when the struct flow actually becomes big
>> enough to require a second map.  This negates the performance gained
>> in the "Pre-compute stage masks" patch earlier in the series.
>> 
>> Requested-by: Ben Pfaff <blp at nicira.com>
>> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
> 
> In flowmap_are_set(), I think the test for "unit + 1 < FLOWMAP_UNITS" is
> unnecessary, since the test "idx + n_bits > MAP_T_BITS" should never be
> true at the same time unless there is a bug in the function parameters.
> Ditto for flowmap_set(), flowmap_clear().
> 

OK.

> flowmap_are_set() implicitly supports a span of 'n_bits' across at most
> two units.  That seems fine but maybe there should be a build assertion
> of some kind, e.g. on FLOWMAP_UNITS <= 2, or maybe documentation that
> 'n_bits' must be <= MAP_T_BITS.
> 

I went with the last suggestion above.

> I think that flowmap_are_set() and flowmap_set() compute the same
> n_bits_mask, but they do so in different ways, not sure why.  Ditto for
> flowmap_clear().
> 

No reason. I changed the latter two to use the simpler form.

> I think that the FLOW_U64_OFFSET and FLOW_U64_OFFREM macro expansions
> should be parenthesized.
> 

OK.

> In FLOW_U64_SIZE, you can use MEMBER_SIZEOF.
> 

OK.

> Here are some suggestions as an incremental diff, please feel free to
> accept or ignore them:
> 
> diff --git a/lib/flow.h b/lib/flow.h
> index 958e7cb..9fa0c99 100644
> --- a/lib/flow.h
> +++ b/lib/flow.h
> @@ -27,6 +27,7 @@
> #include "openflow/openflow.h"
> #include "packets.h"
> #include "hash.h"
> +#include "type-props.h"
> #include "util.h"
> 
> struct dpif_flow_stats;
> @@ -197,8 +198,8 @@ BUILD_ASSERT_DECL(FLOW_SEGMENT_3_ENDS_AT < sizeof(struct flow));
> 
> extern const uint8_t flow_segment_u64s[];
> 
> -#define FLOW_U64_OFFSET(FIELD) offsetof(struct flow, FIELD) / sizeof(uint64_t)
> -#define FLOW_U64_OFFREM(FIELD) offsetof(struct flow, FIELD) % sizeof(uint64_t)
> +#define FLOW_U64_OFFSET(FIELD) (offsetof(struct flow, FIELD) / sizeof(uint64_t))
> +#define FLOW_U64_OFFREM(FIELD) (offsetof(struct flow, FIELD) % sizeof(uint64_t))
> 

Done.

> /* Number of 64-bit units spanned by a 'FIELD'. */
> #define FLOW_U64_SIZE(FIELD)                                            \
> @@ -394,9 +395,7 @@ bool flow_equal_except(const struct flow *a, const struct flow *b,
> typedef unsigned long long map_t;
> #define MAP_T_BITS (sizeof(map_t) * CHAR_BIT)
> #define MAP_1 (map_t)1
> -#define MAP_MAX ULLONG_MAX
> -
> -#define MAP_IS_SET(MAP, IDX) ((MAP) & (MAP_1 << (IDX)))
> +#define MAP_MAX TYPE_MAXIMUM(map_t)
> 
> /* Iterate through the indices of all 1-bits in 'MAP'. */
> #define MAP_FOR_EACH_INDEX(IDX, MAP)            \
> @@ -478,7 +477,7 @@ flowmap_equal(struct flowmap a, struct flowmap b)
> static inline bool
> flowmap_is_set(const struct flowmap *fm, unsigned int idx)
> {
> -    return MAP_IS_SET(fm->bits[idx / MAP_T_BITS], idx % MAP_T_BITS);
> +    return (fm->bits[idx / MAP_T_BITS] & (MAP_1 << (idx % MAP_T_BITS))) != 0;
> }
> 

Right, MAP_IS_SET was used only here. Also, forgot about the explicit bool conversion.

> /* Returns 'true' if any of the 'n_bits' bits starting at 'idx' are set in
> @@ -597,16 +596,17 @@ struct flowmap_aux {
> static inline bool
> flowmap_next_index(struct flowmap_aux *aux, unsigned int *idx)
> {
> -    map_t *map;
> -
> -    while (!*(map = &aux->map.bits[aux->unit])) {
> -        if (++aux->unit == FLOWMAP_UNITS) {
> +    for (;;) {
> +        map_t *map = &aux->map.bits[aux->unit];
> +        if (*map) {
> +            *idx = aux->unit * MAP_T_BITS + raw_ctz(*map);
> +            *map = zero_rightmost_1bit(*map);
> +            return true;
> +        }
> +        if (++aux->unit >= FLOWMAP_UNITS) {
>             return false;
>         }
>     }
> -    *idx = aux->unit * MAP_T_BITS + raw_ctz(*map);
> -    *map = zero_rightmost_1bit(*map);
> -    return true;
> }
> 
> 

Applied.

> 
> 
> Acked-by: Ben Pfaff <blp at nicira.com <mailto:blp at nicira.com>>

Thanks for the review!

Pushed to master,

  Jarno




More information about the dev mailing list