X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fflow.c;h=9c9adc51eddf7bb889c3a3da77b19fa6cfe7f3dd;hb=HEAD;hp=c6e5e070f28ae547c90cd43052c27989e2e914ad;hpb=b7807e4f64c8c64bb6000767de72368306a95c90;p=sliver-openvswitch.git

diff --git a/lib/flow.c b/lib/flow.c
index c6e5e070f..9c9adc51e 100644
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -344,26 +344,29 @@ void
 flow_extract(struct ofpbuf *packet, const struct pkt_metadata *md,
              struct flow *flow)
 {
-    uint32_t buf[FLOW_U32S];
-    struct miniflow mf;
+    struct {
+        struct miniflow mf;
+        uint32_t buf[FLOW_U32S];
+    } m;
 
     COVERAGE_INC(flow_extract);
 
-    miniflow_initialize(&mf, buf);
-    miniflow_extract(packet, md, &mf);
-    miniflow_expand(&mf, flow);
+    miniflow_initialize(&m.mf, m.buf);
+    miniflow_extract(packet, md, &m.mf);
+    miniflow_expand(&m.mf, flow);
 }
 
-/* Caller is responsible for initializing 'dst->values' with enough storage
- * (FLOW_U64S * 8 bytes is enough). */
+/* Caller is responsible for initializing 'dst' with enough storage for
+ * FLOW_U32S * 4 bytes. */
 void
 miniflow_extract(struct ofpbuf *packet, const struct pkt_metadata *md,
                  struct miniflow *dst)
 {
     void *data = ofpbuf_data(packet);
     size_t size = ofpbuf_size(packet);
+    uint32_t *values = miniflow_values(dst);
+    struct mf_ctx mf = { 0, values, values + FLOW_U32S };
     char *l2;
-    struct mf_ctx mf = { 0, dst->values, dst->values + FLOW_U32S };
     ovs_be16 dl_type;
     uint8_t nw_frag, nw_tos, nw_ttl, nw_proto;
 
@@ -823,65 +826,6 @@ flow_wildcards_or(struct flow_wildcards *dst,
     }
 }
 
-/* Perform a bitwise OR of miniflow 'src' flow data with the equivalent
- * fields in 'dst', storing the result in 'dst'. */
-static void
-flow_union_with_miniflow(struct flow *dst, const struct miniflow *src)
-{
-    uint32_t *dst_u32 = (uint32_t *) dst;
-    const uint32_t *p = src->values;
-    uint64_t map;
-
-    for (map = src->map; map; map = zero_rightmost_1bit(map)) {
-        dst_u32[raw_ctz(map)] |= *p++;
-    }
-}
-
-/* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */
-void
-flow_wildcards_fold_minimask(struct flow_wildcards *wc,
-                             const struct minimask *mask)
-{
-    flow_union_with_miniflow(&wc->masks, &mask->masks);
-}
-
-uint64_t
-miniflow_get_map_in_range(const struct miniflow *miniflow,
-                          uint8_t start, uint8_t end, unsigned int *offset)
-{
-    uint64_t map = miniflow->map;
-    *offset = 0;
-
-    if (start > 0) {
-        uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */
-        *offset = count_1bits(map & msk);
-        map &= ~msk;
-    }
-    if (end < FLOW_U32S) {
-        uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */
-        map &= msk;
-    }
-    return map;
-}
-
-/* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask
- * in range [start, end). */
-void
-flow_wildcards_fold_minimask_range(struct flow_wildcards *wc,
-                                   const struct minimask *mask,
-                                   uint8_t start, uint8_t end)
-{
-    uint32_t *dst_u32 = (uint32_t *)&wc->masks;
-    unsigned int offset;
-    uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
-                                             &offset);
-    const uint32_t *p = mask->masks.values + offset;
-
-    for (; map; map = zero_rightmost_1bit(map)) {
-        dst_u32[raw_ctz(map)] |= *p++;
-    }
-}
-
 /* Returns a hash of the wildcards in 'wc'. */
 uint32_t
 flow_wildcards_hash(const struct flow_wildcards *wc, uint32_t basis)
@@ -943,23 +887,76 @@ flow_wildcards_set_reg_mask(struct flow_wildcards *wc, int idx, uint32_t mask)
     wc->masks.regs[idx] = mask;
 }
 
+/* Calculates the 5-tuple hash from the given miniflow.
+ * This returns the same value as flow_hash_5tuple for the corresponding
+ * flow. */
+uint32_t
+miniflow_hash_5tuple(const struct miniflow *flow, uint32_t basis)
+{
+    uint32_t hash = basis;
+
+    if (flow) {
+        ovs_be16 dl_type = MINIFLOW_GET_BE16(flow, dl_type);
+
+        hash = mhash_add(hash, MINIFLOW_GET_U8(flow, nw_proto));
+
+        /* Separate loops for better optimization. */
+        if (dl_type == htons(ETH_TYPE_IPV6)) {
+            uint64_t map = MINIFLOW_MAP(ipv6_src) | MINIFLOW_MAP(ipv6_dst)
+                | MINIFLOW_MAP(tp_src); /* Covers both ports */
+            uint32_t value;
+
+            MINIFLOW_FOR_EACH_IN_MAP(value, flow, map) {
+                hash = mhash_add(hash, value);
+            }
+        } else {
+            uint64_t map = MINIFLOW_MAP(nw_src) | MINIFLOW_MAP(nw_dst)
+                | MINIFLOW_MAP(tp_src); /* Covers both ports */
+            uint32_t value;
+
+            MINIFLOW_FOR_EACH_IN_MAP(value, flow, map) {
+                hash = mhash_add(hash, value);
+            }
+        }
+        hash = mhash_finish(hash, 42); /* Arbitrary number. */
+    }
+    return hash;
+}
+
+BUILD_ASSERT_DECL(offsetof(struct flow, tp_src) + 2
+                  == offsetof(struct flow, tp_dst) &&
+                  offsetof(struct flow, tp_src) / 4
+                  == offsetof(struct flow, tp_dst) / 4);
+BUILD_ASSERT_DECL(offsetof(struct flow, ipv6_src) + 16
+                  == offsetof(struct flow, ipv6_dst));
+
 /* Calculates the 5-tuple hash from the given flow. */
 uint32_t
 flow_hash_5tuple(const struct flow *flow, uint32_t basis)
 {
-    uint32_t hash = 0;
+    uint32_t hash = basis;
 
-    if (!flow) {
-        return 0;
-    }
+    if (flow) {
+        const uint32_t *flow_u32 = (const uint32_t *)flow;
 
-    hash = mhash_add(basis, (OVS_FORCE uint32_t) flow->nw_src);
-    hash = mhash_add(hash, (OVS_FORCE uint32_t) flow->nw_dst);
-    hash = mhash_add(hash, ((OVS_FORCE uint32_t) flow->tp_src << 16)
-                           | (OVS_FORCE uint32_t) flow->tp_dst);
-    hash = mhash_add(hash, flow->nw_proto);
+        hash = mhash_add(hash, flow->nw_proto);
+
+        if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
+            int ofs = offsetof(struct flow, ipv6_src) / 4;
+            int end = ofs + 2 * sizeof flow->ipv6_src / 4;
+
+            while (ofs < end) {
+                hash = mhash_add(hash, flow_u32[ofs++]);
+            }
+        } else {
+            hash = mhash_add(hash, (OVS_FORCE uint32_t) flow->nw_src);
+            hash = mhash_add(hash, (OVS_FORCE uint32_t) flow->nw_dst);
+        }
+        hash = mhash_add(hash, flow_u32[offsetof(struct flow, tp_src) / 4]);
 
-    return mhash_finish(hash, 13);
+        hash = mhash_finish(hash, 42); /* Arbitrary number. */
+    }
+    return hash;
 }
 
 /* Hashes 'flow' based on its L2 through L4 protocol information. */
@@ -1581,11 +1578,16 @@ miniflow_n_values(const struct miniflow *flow)
 static uint32_t *
 miniflow_alloc_values(struct miniflow *flow, int n)
 {
-    if (n <= MINI_N_INLINE) {
+    int size = MINIFLOW_VALUES_SIZE(n);
+
+    if (size <= sizeof flow->inline_values) {
+        flow->values_inline = true;
         return flow->inline_values;
     } else {
         COVERAGE_INC(miniflow_malloc);
-        return xmalloc(n * sizeof *flow->values);
+        flow->values_inline = false;
+        flow->offline_values = xmalloc(size);
+        return flow->offline_values;
     }
 }
 
@@ -1598,25 +1600,24 @@ miniflow_alloc_values(struct miniflow *flow, int n)
  * 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 initializes 'dst->values' (either inline if possible or with
+ * This function initializes values (either inline if possible or with
  * malloc() otherwise) and copies the uint32_t elements of 'src' indicated by
  * 'dst->map' into it. */
 static void
 miniflow_init__(struct miniflow *dst, const struct flow *src, int n)
 {
     const uint32_t *src_u32 = (const uint32_t *) src;
-    unsigned int ofs;
+    uint32_t *dst_u32 = miniflow_alloc_values(dst, n);
     uint64_t map;
 
-    dst->values = miniflow_alloc_values(dst, n);
-    ofs = 0;
     for (map = dst->map; map; map = zero_rightmost_1bit(map)) {
-        dst->values[ofs++] = src_u32[raw_ctz(map)];
+        *dst_u32++ = src_u32[raw_ctz(map)];
     }
 }
 
 /* Initializes 'dst' as a copy of 'src'.  The caller must eventually free 'dst'
- * with miniflow_destroy(). */
+ * with miniflow_destroy().
+ * Always allocates offline storage. */
 void
 miniflow_init(struct miniflow *dst, const struct flow *src)
 {
@@ -1653,25 +1654,57 @@ miniflow_init_with_minimask(struct miniflow *dst, const struct flow *src,
 void
 miniflow_clone(struct miniflow *dst, const struct miniflow *src)
 {
-    int n = miniflow_n_values(src);
+    int size = MINIFLOW_VALUES_SIZE(miniflow_n_values(src));
+    uint32_t *values;
+
+    dst->map = src->map;
+    if (size <= sizeof dst->inline_values) {
+        dst->values_inline = true;
+        values = dst->inline_values;
+    } else {
+        dst->values_inline = false;
+        COVERAGE_INC(miniflow_malloc);
+        dst->offline_values = xmalloc(size);
+        values = dst->offline_values;
+    }
+    memcpy(values, miniflow_get_values(src), size);
+}
+
+/* Initializes 'dst' as a copy of 'src'.  The caller must have allocated
+ * 'dst' to have inline space all data in 'src'. */
+void
+miniflow_clone_inline(struct miniflow *dst, const struct miniflow *src,
+                      size_t n_values)
+{
+    dst->values_inline = true;
     dst->map = src->map;
-    dst->values = miniflow_alloc_values(dst, n);
-    memcpy(dst->values, src->values, n * sizeof *dst->values);
+    memcpy(dst->inline_values, miniflow_get_values(src),
+           MINIFLOW_VALUES_SIZE(n_values));
 }
 
 /* Initializes 'dst' with the data in 'src', destroying 'src'.
- * The caller must eventually free 'dst' with miniflow_destroy(). */
+ * The caller must eventually free 'dst' with miniflow_destroy().
+ * 'dst' must be regularly sized miniflow, but 'src' can have
+ * larger than default inline values. */
 void
 miniflow_move(struct miniflow *dst, struct miniflow *src)
 {
-    if (src->values == src->inline_values) {
-        dst->values = dst->inline_values;
-        memcpy(dst->values, src->values,
-               miniflow_n_values(src) * sizeof *dst->values);
+    int size = MINIFLOW_VALUES_SIZE(miniflow_n_values(src));
+
+    dst->map = src->map;
+    if (size <= sizeof dst->inline_values) {
+        dst->values_inline = true;
+        memcpy(dst->inline_values, miniflow_get_values(src), size);
+        miniflow_destroy(src);
+    } else if (src->values_inline) {
+        dst->values_inline = false;
+        COVERAGE_INC(miniflow_malloc);
+        dst->offline_values = xmalloc(size);
+        memcpy(dst->offline_values, src->inline_values, size);
     } else {
-        dst->values = src->values;
+        dst->values_inline = false;
+        dst->offline_values = src->offline_values;
     }
-    dst->map = src->map;
 }
 
 /* Frees any memory owned by 'flow'.  Does not free the storage in which 'flow'
@@ -1679,8 +1712,8 @@ miniflow_move(struct miniflow *dst, struct miniflow *src)
 void
 miniflow_destroy(struct miniflow *flow)
 {
-    if (flow->values != flow->inline_values) {
-        free(flow->values);
+    if (!flow->values_inline) {
+        free(flow->offline_values);
     }
 }
 
@@ -1698,7 +1731,7 @@ static uint32_t
 miniflow_get(const struct miniflow *flow, unsigned int u32_ofs)
 {
     return (flow->map & UINT64_C(1) << u32_ofs)
-        ? *(flow->values +
+        ? *(miniflow_get_u32_values(flow) +
             count_1bits(flow->map & ((UINT64_C(1) << u32_ofs) - 1)))
         : 0;
 }
@@ -1707,19 +1740,22 @@ miniflow_get(const struct miniflow *flow, unsigned int u32_ofs)
 bool
 miniflow_equal(const struct miniflow *a, const struct miniflow *b)
 {
-    const uint32_t *ap = a->values;
-    const uint32_t *bp = b->values;
+    const uint32_t *ap = miniflow_get_u32_values(a);
+    const uint32_t *bp = miniflow_get_u32_values(b);
     const uint64_t a_map = a->map;
     const uint64_t b_map = b->map;
-    uint64_t map;
 
-    if (a_map == b_map) {
-        for (map = a_map; map; map = zero_rightmost_1bit(map)) {
+    if (OVS_LIKELY(a_map == b_map)) {
+        int count = miniflow_n_values(a);
+
+        while (count--) {
             if (*ap++ != *bp++) {
                 return false;
             }
         }
     } else {
+        uint64_t map;
+
         for (map = a_map | b_map; map; map = zero_rightmost_1bit(map)) {
             uint64_t bit = rightmost_1bit(map);
             uint64_t a_value = a_map & bit ? *ap++ : 0;
@@ -1740,18 +1776,15 @@ bool
 miniflow_equal_in_minimask(const struct miniflow *a, const struct miniflow *b,
                            const struct minimask *mask)
 {
-    const uint32_t *p;
+    const uint32_t *p = miniflow_get_u32_values(&mask->masks);
     uint64_t map;
 
-    p = mask->masks.values;
-
     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
         int ofs = raw_ctz(map);
 
-        if ((miniflow_get(a, ofs) ^ miniflow_get(b, ofs)) & *p) {
+        if ((miniflow_get(a, ofs) ^ miniflow_get(b, ofs)) & *p++) {
             return false;
         }
-        p++;
     }
 
     return true;
@@ -1764,114 +1797,20 @@ miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow *b,
                                 const struct minimask *mask)
 {
     const uint32_t *b_u32 = (const uint32_t *) b;
-    const uint32_t *p;
+    const uint32_t *p = miniflow_get_u32_values(&mask->masks);
     uint64_t map;
 
-    p = mask->masks.values;
-
     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
         int ofs = raw_ctz(map);
 
-        if ((miniflow_get(a, ofs) ^ b_u32[ofs]) & *p) {
+        if ((miniflow_get(a, ofs) ^ b_u32[ofs]) & *p++) {
             return false;
         }
-        p++;
     }
 
     return true;
 }
 
-/* Returns a hash value for 'flow', given 'basis'. */
-uint32_t
-miniflow_hash(const struct miniflow *flow, uint32_t basis)
-{
-    const uint32_t *p = flow->values;
-    uint32_t hash = basis;
-    uint64_t hash_map = 0;
-    uint64_t map;
-
-    for (map = flow->map; map; map = zero_rightmost_1bit(map)) {
-        if (*p) {
-            hash = mhash_add(hash, *p);
-            hash_map |= rightmost_1bit(map);
-        }
-        p++;
-    }
-    hash = mhash_add(hash, hash_map);
-    hash = mhash_add(hash, hash_map >> 32);
-
-    return mhash_finish(hash, p - flow->values);
-}
-
-/* Returns a hash value for the bits of 'flow' where there are 1-bits in
- * 'mask', given 'basis'.
- *
- * The hash values returned by this function are the same as those returned by
- * flow_hash_in_minimask(), only the form of the arguments differ. */
-uint32_t
-miniflow_hash_in_minimask(const struct miniflow *flow,
-                          const struct minimask *mask, uint32_t basis)
-{
-    const uint32_t *p = mask->masks.values;
-    uint32_t hash;
-    uint64_t map;
-
-    hash = basis;
-
-    for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
-        hash = mhash_add(hash, miniflow_get(flow, raw_ctz(map)) & *p++);
-    }
-
-    return mhash_finish(hash, (p - mask->masks.values) * 4);
-}
-
-/* Returns a hash value for the bits of 'flow' where there are 1-bits in
- * 'mask', given 'basis'.
- *
- * The hash values returned by this function are the same as those returned by
- * miniflow_hash_in_minimask(), only the form of the arguments differ. */
-uint32_t
-flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
-                      uint32_t basis)
-{
-    const uint32_t *flow_u32 = (const uint32_t *)flow;
-    const uint32_t *p = mask->masks.values;
-    uint32_t hash;
-    uint64_t map;
-
-    hash = basis;
-    for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
-        hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++);
-    }
-
-    return mhash_finish(hash, (p - mask->masks.values) * 4);
-}
-
-/* Returns a hash value for the bits of range [start, end) in 'flow',
- * where there are 1-bits in 'mask', given 'hash'.
- *
- * The hash values returned by this function are the same as those returned by
- * minimatch_hash_range(), only the form of the arguments differ. */
-uint32_t
-flow_hash_in_minimask_range(const struct flow *flow,
-                            const struct minimask *mask,
-                            uint8_t start, uint8_t end, uint32_t *basis)
-{
-    const uint32_t *flow_u32 = (const uint32_t *)flow;
-    unsigned int offset;
-    uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
-                                             &offset);
-    const uint32_t *p = mask->masks.values + offset;
-    uint32_t hash = *basis;
-
-    for (; map; map = zero_rightmost_1bit(map)) {
-        hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++);
-    }
-
-    *basis = hash; /* Allow continuation from the unfinished value. */
-    return mhash_finish(hash, (p - mask->masks.values) * 4);
-}
-
 
 /* Initializes 'dst' as a copy of 'src'.  The caller must eventually free 'dst'
  * with minimask_destroy(). */
@@ -1907,12 +1846,14 @@ minimask_combine(struct minimask *dst_,
                  uint32_t storage[FLOW_U32S])
 {
     struct miniflow *dst = &dst_->masks;
+    uint32_t *dst_values = storage;
     const struct miniflow *a = &a_->masks;
     const struct miniflow *b = &b_->masks;
     uint64_t map;
     int n = 0;
 
-    dst->values = storage;
+    dst->values_inline = false;
+    dst->offline_values = storage;
 
     dst->map = 0;
     for (map = a->map & b->map; map; map = zero_rightmost_1bit(map)) {
@@ -1921,7 +1862,7 @@ minimask_combine(struct minimask *dst_,
 
         if (mask) {
             dst->map |= rightmost_1bit(map);
-            dst->values[n++] = mask;
+            dst_values[n++] = mask;
         }
     }
 }
@@ -1956,26 +1897,17 @@ minimask_equal(const struct minimask *a, const struct minimask *b)
     return miniflow_equal(&a->masks, &b->masks);
 }
 
-/* Returns a hash value for 'mask', given 'basis'. */
-uint32_t
-minimask_hash(const struct minimask *mask, uint32_t basis)
-{
-    return miniflow_hash(&mask->masks, basis);
-}
-
-/* Returns true if at least one bit is wildcarded in 'a_' but not in 'b_',
+/* Returns true if at least one bit matched by 'b' is wildcarded by 'a',
  * false otherwise. */
 bool
-minimask_has_extra(const struct minimask *a_, const struct minimask *b_)
+minimask_has_extra(const struct minimask *a, const struct minimask *b)
 {
-    const struct miniflow *a = &a_->masks;
-    const struct miniflow *b = &b_->masks;
+    const uint32_t *p = miniflow_get_u32_values(&b->masks);
     uint64_t map;
 
-    for (map = a->map | b->map; map; map = zero_rightmost_1bit(map)) {
-        int ofs = raw_ctz(map);
-        uint32_t a_u32 = miniflow_get(a, ofs);
-        uint32_t b_u32 = miniflow_get(b, ofs);
+    for (map = b->masks.map; map; map = zero_rightmost_1bit(map)) {
+        uint32_t a_u32 = minimask_get(a, raw_ctz(map));
+        uint32_t b_u32 = *p++;
 
         if ((a_u32 & b_u32) != b_u32) {
             return true;
@@ -1984,20 +1916,3 @@ minimask_has_extra(const struct minimask *a_, const struct minimask *b_)
 
     return false;
 }
-
-/* Returns true if 'mask' matches every packet, false if 'mask' fixes any bits
- * or fields. */
-bool
-minimask_is_catchall(const struct minimask *mask_)
-{
-    const struct miniflow *mask = &mask_->masks;
-    const uint32_t *p = mask->values;
-    uint64_t map;
-
-    for (map = mask->map; map; map = zero_rightmost_1bit(map)) {
-        if (*p++) {
-            return false;
-        }
-    }
-    return true;
-}