[ovs-dev] [RFC PATCH v2 4/7] match: Single malloc minimatch.

Jarno Rajahalme jrajahalme at nicira.com
Fri Jul 10 17:35:22 UTC 2015


Allocate the miniflow and minimask in struct minimatch at once, so
that they are consecutive in memory.  This halves the number of
allocations, and allows smaller minimatches to share the same cache
line.

After this a minimatch has one heap allocation for all it's data.
Previously it had either none (when data was small enough to fit in
struct miniflow's inline buffer), or two (when the inline buffer was
insufficient).  Hopefully always having one performs almost the same
as none or two, in average.

Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
 lib/flow.c  |   87 +++++++++++++++++++++++++++++++++++------------------------
 lib/flow.h  |    9 +++++--
 lib/match.c |   17 ++++++++----
 lib/match.h |   12 +++++++--
 4 files changed, 81 insertions(+), 44 deletions(-)

diff --git a/lib/flow.c b/lib/flow.c
index ca8163e..b3bfca9 100644
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -2006,62 +2006,74 @@ miniflow_n_values(const struct miniflow *flow)
 }
 
 /* Completes an initialization of 'dst' as a miniflow copy of 'src' begun by
- * the caller.  The caller must have already computed 'map' properly
+ * the caller.  The caller must have already computed 'dst->map' properly
  * to indicate the significant uint64_t elements of 'src'.
  *
  * Normally the significant elements are the ones that are non-zero.  However,
  * when a miniflow is initialized from a (mini)mask, the values can be zeroes,
- * so that the flow and mask always have the same maps.
- *
- * This function always dynamically allocates a miniflow with the correct
- * amount of inline storage and copies the uint64_t elements of 'src' indicated
- * by 'map' into it. */
-static struct miniflow *
-miniflow_init__(const struct flow *src, uint64_t map)
+ * so that the flow and mask always have the same maps. */
+void
+miniflow_init(struct miniflow *dst, const struct flow *src)
 {
     const uint64_t *src_u64 = (const uint64_t *) src;
-    struct miniflow *dst = xmalloc(sizeof *dst
-                                   + MINIFLOW_VALUES_SIZE(count_1bits(map)));
     uint64_t *dst_u64 = dst->values;
     int idx;
 
-    COVERAGE_INC(miniflow_malloc);
-
-    dst->map = map;
-    MAP_FOR_EACH_INDEX(idx, map) {
+    MAP_FOR_EACH_INDEX(idx, dst->map) {
         *dst_u64++ = src_u64[idx];
     }
-    return dst;
 }
 
-/* Returns a miniflow copy of 'src'.  The caller must eventually free the
- * returned miniflow with free(). */
-struct miniflow *
-miniflow_create(const struct flow *src)
+/* Initialize the map of 'flow' from 'src'. */
+void
+miniflow_map_init(struct miniflow *flow, const struct flow *src)
 {
     const uint64_t *src_u64 = (const uint64_t *) src;
-    uint64_t map;
-    unsigned int i;
-
-    /* Initialize dst->map, counting the number of nonzero elements. */
-    map = 0;
+    int i;
 
+    /* Initialize map, counting the number of nonzero elements. */
+    flow->map = 0;
     for (i = 0; i < FLOW_U64S; i++) {
         if (src_u64[i]) {
-            map |= UINT64_C(1) << i;
+            flow->map |= UINT64_C(1) << i;
         }
     }
+}
 
-    return miniflow_init__(src, map);
+/* Allocates 'n' count of miniflows, consecutive in memory, initializing the
+ * map of each from 'src'.
+ * Returns the size of the miniflow data. */
+size_t
+miniflow_alloc(struct miniflow *dsts[], size_t n, const struct miniflow *src)
+{
+    size_t data_size = MINIFLOW_VALUES_SIZE(count_1bits(src->map));
+    size_t size = sizeof *src + data_size;
+    struct miniflow *dst = xmalloc(n * size);
+    unsigned int i;
+
+    COVERAGE_INC(miniflow_malloc);
+
+    for (i = 0; i < n; i++) {
+        dst->map = src->map;
+        dsts[i] = dst;
+        dst += size / sizeof *dst;
+    }
+    return data_size;
 }
 
-/* Returns a copy of 'src', using 'mask->map'.  The caller must eventually free
- * the returned miniflow with free(). */
+/* Returns a miniflow copy of 'src'.  The caller must eventually free() the
+ * returned miniflow. */
 struct miniflow *
-miniflow_create_with_minimask(const struct flow *src,
-                              const struct minimask *mask)
+miniflow_create(const struct flow *src)
 {
-    return miniflow_init__(src, mask->masks.map);
+    struct miniflow tmp;
+    struct miniflow *dst;
+
+    miniflow_map_init(&tmp, src);
+
+    miniflow_alloc(&dst, 1, &tmp);
+    miniflow_init(dst, src);
+    return dst;
 }
 
 /* Returns a copy of 'src'.  The caller must eventually free the returned
@@ -2070,11 +2082,10 @@ struct miniflow *
 miniflow_clone(const struct miniflow *src)
 {
     struct miniflow *dst;
-    int n = miniflow_n_values(src);
+    size_t data_size;
 
-    COVERAGE_INC(miniflow_malloc);
-    dst = xmalloc(sizeof *dst + MINIFLOW_VALUES_SIZE(n));
-    miniflow_clone_inline(dst, src, n);
+    data_size = miniflow_alloc(&dst, 1, src);
+    memcpy(dst->values, src->values, data_size);
     return dst;
 }
 
@@ -2160,6 +2171,12 @@ miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow *b,
 }
 
 
+void
+minimask_init(struct minimask *mask, const struct flow_wildcards *wc)
+{
+    miniflow_init(&mask->masks, &wc->masks);
+}
+
 /* Returns a minimask copy of 'wc'.  The caller must eventually free the
  * returned minimask with free(). */
 struct minimask *
diff --git a/lib/flow.h b/lib/flow.h
index 6269b1d..d242588 100644
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -398,10 +398,14 @@ struct pkt_metadata;
  * 'dst->map' is ignored on input and set on output to indicate which fields
  * were extracted. */
 void miniflow_extract(struct dp_packet *packet, struct miniflow *dst);
+void miniflow_map_init(struct miniflow *, const struct flow *);
+size_t miniflow_alloc(struct miniflow *dsts[], size_t n,
+                      const struct miniflow *src);
+void miniflow_init(struct miniflow *, const struct flow *);
+
 struct miniflow * miniflow_create(const struct flow *);
-struct miniflow * miniflow_create_with_minimask(const struct flow *,
-                                              const struct minimask *);
 struct miniflow * miniflow_clone(const struct miniflow *);
+
 void miniflow_clone_inline(struct miniflow *, const struct miniflow *,
                            size_t n_values);
 
@@ -559,6 +563,7 @@ struct minimask {
     struct miniflow masks;
 };
 
+void minimask_init(struct minimask *, const struct flow_wildcards *);
 struct minimask * minimask_create(const struct flow_wildcards *);
 struct minimask * minimask_clone(const struct minimask *);
 void minimask_combine(struct minimask *dst,
diff --git a/lib/match.c b/lib/match.c
index 2119ed7..6d4f1a3 100644
--- a/lib/match.c
+++ b/lib/match.c
@@ -1195,8 +1195,13 @@ match_print(const struct match *match)
 void
 minimatch_init(struct minimatch *dst, const struct match *src)
 {
-    dst->mask = minimask_create(&src->wc);
-    dst->flow = miniflow_create_with_minimask(&src->flow, dst->mask);
+    struct miniflow tmp;
+
+    miniflow_map_init(&tmp, &src->wc.masks);
+    /* Allocate two consecutive miniflows. */
+    miniflow_alloc(dst->flows, 2, &tmp);
+    miniflow_init(dst->flow, &src->flow);
+    minimask_init(dst->mask, &src->wc);
 }
 
 /* Initializes 'dst' as a copy of 'src'.  The caller must eventually free 'dst'
@@ -1204,8 +1209,11 @@ minimatch_init(struct minimatch *dst, const struct match *src)
 void
 minimatch_clone(struct minimatch *dst, const struct minimatch *src)
 {
-    dst->flow = miniflow_clone(src->flow);
-    dst->mask = minimask_clone(src->mask);
+    /* Allocate two consecutive miniflows. */
+    size_t data_size = miniflow_alloc(dst->flows, 2, &src->mask->masks);
+
+    memcpy(dst->flow->values, src->flow->values, data_size);
+    memcpy(dst->mask->masks.values, src->mask->masks.values, data_size);
 }
 
 /* Initializes 'dst' with the data in 'src', destroying 'src'.  The caller must
@@ -1223,7 +1231,6 @@ void
 minimatch_destroy(struct minimatch *match)
 {
     free(match->flow);
-    free(match->mask);
 }
 
 /* Initializes 'dst' as a copy of 'src'. */
diff --git a/lib/match.h b/lib/match.h
index c664a6e..6356a55 100644
--- a/lib/match.h
+++ b/lib/match.h
@@ -160,6 +160,9 @@ void match_print(const struct match *);
 
 /* A sparse representation of a "struct match".
  *
+ * 'flows' is used for allocating both 'flow' and 'mask' with one
+ * miniflow_alloc() call.
+ *
  * There are two invariants:
  *
  *   - The same invariant as "struct match", that is, a 1-bit in the 'flow'
@@ -170,8 +173,13 @@ void match_print(const struct match *);
  *     'values', which makes minimatch_matches_flow() faster.
  */
 struct minimatch {
-    struct miniflow *flow;
-    struct minimask *mask;
+    union {
+        struct {
+            struct miniflow *flow;
+            struct minimask *mask;
+        };
+        struct miniflow *flows[2];
+    };
 };
 
 void minimatch_init(struct minimatch *, const struct match *);
-- 
1.7.10.4




More information about the dev mailing list