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

[Ben Pfaff]

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().

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 <blp at nicira.com>