> On Aug 26, 2015, at 10:06 AM, Ben Pfaff <b...@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 <b...@nicira.com>
>> Signed-off-by: Jarno Rajahalme <jrajaha...@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 <b...@nicira.com <mailto:b...@nicira.com>>
Thanks for the review!
Pushed to master,
Jarno
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
