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().
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 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().
I think that the FLOW_U64_OFFSET and FLOW_U64_OFFREM macro expansions
should be parenthesized.
In FLOW_U64_SIZE, you can use MEMBER_SIZEOF.
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))
/* 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;
}
/* 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;
}
Acked-by: Ben Pfaff <b...@nicira.com>
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
