From 27bbe15dec4e1862396b5c4d265f0ced71b49930 Mon Sep 17 00:00:00 2001 From: Jarno Rajahalme Date: Tue, 29 Apr 2014 15:50:39 -0700 Subject: [PATCH] lib/flow: Maintain miniflow offline values explicitly. This allows use of miniflows that have all of their values inline. Signed-off-by: Jarno Rajahalme Acked-by: Ethan Jackson --- lib/classifier.c | 36 ++++++++++--------- lib/dpif-netdev.c | 32 +++++++++-------- lib/flow.c | 91 +++++++++++++++++++++++------------------------ lib/flow.h | 70 ++++++++++++++++++++++-------------- lib/match.c | 4 +-- 5 files changed, 127 insertions(+), 106 deletions(-) diff --git a/lib/classifier.c b/lib/classifier.c index 74ef2aec8..a8f9e4f5f 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -40,7 +40,7 @@ struct cls_trie { struct cls_subtable_entry { struct cls_subtable *subtable; - uint32_t *mask_values; + const uint32_t *mask_values; tag_type tag; unsigned int max_priority; }; @@ -278,8 +278,9 @@ static inline uint32_t flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask, uint32_t basis) { + const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks); const uint32_t *flow_u32 = (const uint32_t *)flow; - const uint32_t *p = mask->masks.values; + const uint32_t *p = mask_values; uint32_t hash; uint64_t map; @@ -288,7 +289,7 @@ flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask, hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++); } - return mhash_finish(hash, (p - mask->masks.values) * 4); + return mhash_finish(hash, (p - mask_values) * 4); } /* Returns a hash value for the bits of 'flow' where there are 1-bits in @@ -300,7 +301,8 @@ static inline uint32_t miniflow_hash_in_minimask(const struct miniflow *flow, const struct minimask *mask, uint32_t basis) { - const uint32_t *p = mask->masks.values; + const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks); + const uint32_t *p = mask_values; uint32_t hash = basis; uint32_t flow_u32; @@ -308,7 +310,7 @@ miniflow_hash_in_minimask(const struct miniflow *flow, hash = mhash_add(hash, flow_u32 & *p++); } - return mhash_finish(hash, (p - mask->masks.values) * 4); + return mhash_finish(hash, (p - mask_values) * 4); } /* Returns a hash value for the bits of range [start, end) in 'flow', @@ -321,11 +323,12 @@ 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 *mask_values = miniflow_get_u32_values(&mask->masks); 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; + const uint32_t *p = mask_values + offset; uint32_t hash = *basis; for (; map; map = zero_rightmost_1bit(map)) { @@ -333,7 +336,7 @@ flow_hash_in_minimask_range(const struct flow *flow, } *basis = hash; /* Allow continuation from the unfinished value. */ - return mhash_finish(hash, (p - mask->masks.values) * 4); + return mhash_finish(hash, (p - mask_values) * 4); } /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */ @@ -355,7 +358,7 @@ flow_wildcards_fold_minimask_range(struct flow_wildcards *wc, unsigned int offset; uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end, &offset); - const uint32_t *p = mask->masks.values + offset; + const uint32_t *p = miniflow_get_u32_values(&mask->masks) + offset; for (; map; map = zero_rightmost_1bit(map)) { dst_u32[raw_ctz(map)] |= *p++; @@ -366,7 +369,8 @@ flow_wildcards_fold_minimask_range(struct flow_wildcards *wc, static inline uint32_t miniflow_hash(const struct miniflow *flow, uint32_t basis) { - const uint32_t *p = flow->values; + const uint32_t *values = miniflow_get_u32_values(flow); + const uint32_t *p = values; uint32_t hash = basis; uint64_t hash_map = 0; uint64_t map; @@ -381,7 +385,7 @@ miniflow_hash(const struct miniflow *flow, uint32_t basis) hash = mhash_add(hash, hash_map); hash = mhash_add(hash, hash_map >> 32); - return mhash_finish(hash, p - flow->values); + return mhash_finish(hash, p - values); } /* Returns a hash value for 'mask', given 'basis'. */ @@ -414,8 +418,8 @@ minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end, n = count_1bits(miniflow_get_map_in_range(&match->mask.masks, start, end, &offset)); - q = match->mask.masks.values + offset; - p = match->flow.values + offset; + q = miniflow_get_u32_values(&match->mask.masks) + offset; + p = miniflow_get_u32_values(&match->flow) + offset; for (i = 0; i < n; i++) { hash = mhash_add(hash, p[i] & q[i]); @@ -969,8 +973,8 @@ static bool minimatch_matches_miniflow(const struct minimatch *match, const struct miniflow *target) { - const uint32_t *flowp = (const uint32_t *)match->flow.values; - const uint32_t *maskp = (const uint32_t *)match->mask.masks.values; + const uint32_t *flowp = miniflow_get_u32_values(&match->flow); + const uint32_t *maskp = miniflow_get_u32_values(&match->mask.masks); uint32_t target_u32; MINIFLOW_FOR_EACH_IN_MAP(target_u32, target, match->mask.masks.map) { @@ -1324,7 +1328,7 @@ insert_subtable(struct cls_classifier *cls, const struct minimask *mask) hmap_insert(&cls->subtables, &subtable->hmap_node, hash); elem.subtable = subtable; - elem.mask_values = subtable->mask.masks.values; + elem.mask_values = miniflow_get_values(&subtable->mask.masks); elem.tag = subtable->tag; elem.max_priority = subtable->max_priority; cls_subtable_cache_push_back(&cls->subtables_priority, elem); @@ -1987,7 +1991,7 @@ minimask_get_prefix_len(const struct minimask *minimask, static const ovs_be32 * minimatch_get_prefix(const struct minimatch *match, const struct mf_field *mf) { - return match->flow.values + + return miniflow_get_be32_values(&match->flow) + count_1bits(match->flow.map & ((UINT64_C(1) << mf->flow_be32ofs) - 1)); } diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index 96c5feb42..55712dde1 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -1527,8 +1527,10 @@ dpif_netdev_execute(struct dpif *dpif, struct dpif_execute *execute) { struct dp_netdev *dp = get_dp_netdev(dpif); struct pkt_metadata *md = &execute->md; - struct miniflow key; - uint32_t buf[FLOW_U32S]; + struct { + struct miniflow flow; + uint32_t buf[FLOW_U32S]; + } key; if (ofpbuf_size(execute->packet) < ETH_HEADER_LEN || ofpbuf_size(execute->packet) > UINT16_MAX) { @@ -1536,11 +1538,11 @@ dpif_netdev_execute(struct dpif *dpif, struct dpif_execute *execute) } /* Extract flow key. */ - miniflow_initialize(&key, buf); - miniflow_extract(execute->packet, md, &key); + miniflow_initialize(&key.flow, key.buf); + miniflow_extract(execute->packet, md, &key.flow); ovs_rwlock_rdlock(&dp->port_rwlock); - dp_netdev_execute_actions(dp, &key, execute->packet, false, md, + dp_netdev_execute_actions(dp, &key.flow, execute->packet, false, md, execute->actions, execute->actions_len); ovs_rwlock_unlock(&dp->port_rwlock); @@ -2009,32 +2011,34 @@ dp_netdev_input(struct dp_netdev *dp, struct ofpbuf *packet, OVS_REQ_RDLOCK(dp->port_rwlock) { struct dp_netdev_flow *netdev_flow; - struct miniflow key; - uint32_t buf[FLOW_U32S]; + struct { + struct miniflow flow; + uint32_t buf[FLOW_U32S]; + } key; if (ofpbuf_size(packet) < ETH_HEADER_LEN) { ofpbuf_delete(packet); return; } - miniflow_initialize(&key, buf); - miniflow_extract(packet, md, &key); + miniflow_initialize(&key.flow, key.buf); + miniflow_extract(packet, md, &key.flow); - netdev_flow = dp_netdev_lookup_flow(dp, &key); + netdev_flow = dp_netdev_lookup_flow(dp, &key.flow); if (netdev_flow) { struct dp_netdev_actions *actions; - dp_netdev_flow_used(netdev_flow, packet, &key); + dp_netdev_flow_used(netdev_flow, packet, &key.flow); actions = dp_netdev_flow_get_actions(netdev_flow); - dp_netdev_execute_actions(dp, &key, packet, true, md, + dp_netdev_execute_actions(dp, &key.flow, packet, true, md, actions->actions, actions->size); dp_netdev_count_packet(dp, DP_STAT_HIT); } else if (dp->handler_queues) { dp_netdev_count_packet(dp, DP_STAT_MISS); dp_netdev_output_userspace(dp, packet, - miniflow_hash_5tuple(&key, 0) + miniflow_hash_5tuple(&key.flow, 0) % dp->n_handlers, - DPIF_UC_MISS, &key, NULL); + DPIF_UC_MISS, &key.flow, NULL); ofpbuf_delete(packet); } } diff --git a/lib/flow.c b/lib/flow.c index 211203105..2df7b3db9 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 - * for FLOW_U32S * 4 bytes. */ +/* 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; @@ -1575,11 +1578,14 @@ miniflow_n_values(const struct miniflow *flow) static uint32_t * miniflow_alloc_values(struct miniflow *flow, int n) { - if (n <= MINI_N_INLINE) { + if (n <= sizeof flow->inline_values / sizeof(uint32_t)) { + 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(n * sizeof(uint32_t)); + return flow->offline_values; } } @@ -1592,25 +1598,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) { @@ -1649,8 +1654,8 @@ miniflow_clone(struct miniflow *dst, const struct miniflow *src) { int n = miniflow_n_values(src); dst->map = src->map; - dst->values = miniflow_alloc_values(dst, n); - memcpy(dst->values, src->values, n * sizeof *dst->values); + memcpy(miniflow_alloc_values(dst, n), miniflow_get_values(src), + n * sizeof(uint32_t)); } /* Initializes 'dst' with the data in 'src', destroying 'src'. @@ -1658,14 +1663,7 @@ miniflow_clone(struct miniflow *dst, const struct miniflow *src) 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); - } else { - dst->values = src->values; - } - dst->map = src->map; + *dst = *src; } /* Frees any memory owned by 'flow'. Does not free the storage in which 'flow' @@ -1673,8 +1671,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); } } @@ -1692,7 +1690,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; } @@ -1701,19 +1699,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; @@ -1734,18 +1735,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; @@ -1758,18 +1756,15 @@ 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; @@ -1810,12 +1805,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)) { @@ -1824,7 +1821,7 @@ minimask_combine(struct minimask *dst_, if (mask) { dst->map |= rightmost_1bit(map); - dst->values[n++] = mask; + dst_values[n++] = mask; } } } @@ -1864,7 +1861,7 @@ minimask_equal(const struct minimask *a, const struct minimask *b) bool minimask_has_extra(const struct minimask *a, const struct minimask *b) { - const uint32_t *p = b->masks.values; + const uint32_t *p = miniflow_get_u32_values(&b->masks); uint64_t map; for (map = b->masks.map; map; map = zero_rightmost_1bit(map)) { diff --git a/lib/flow.h b/lib/flow.h index 36d453ae4..795ec18e7 100644 --- a/lib/flow.h +++ b/lib/flow.h @@ -323,7 +323,7 @@ bool flow_equal_except(const struct flow *a, const struct flow *b, /* Compressed flow. */ #define MINI_N_INLINE (sizeof(void *) == 4 ? 7 : 8) -BUILD_ASSERT_DECL(FLOW_U32S <= 64); +BUILD_ASSERT_DECL(FLOW_U32S <= 63); /* A sparse representation of a "struct flow". * @@ -334,42 +334,59 @@ BUILD_ASSERT_DECL(FLOW_U32S <= 64); * * The 'map' member holds one bit for each uint32_t in a "struct flow". Each * 0-bit indicates that the corresponding uint32_t is zero, each 1-bit that it - * *may* be nonzero. + * *may* be nonzero (see below how this applies to minimasks). * - * 'values' points to the start of an array that has one element for each 1-bit - * in 'map'. The least-numbered 1-bit is in values[0], the next 1-bit is in - * values[1], and so on. + * The 'values_inline' boolean member indicates that the values are at + * 'inline_values'. If 'values_inline' is zero, then the values are + * offline at 'offline_values'. In either case, values is an array that has + * one element for each 1-bit in 'map'. The least-numbered 1-bit is in + * the first element of the values array, the next 1-bit is in the next array + * element, and so on. * - * 'values' may point to a few different locations: - * - * - If 'map' has MINI_N_INLINE or fewer 1-bits, it may point to - * 'inline_values'. One hopes that this is the common case. - * - * - If 'map' has more than MINI_N_INLINE 1-bits, it may point to memory - * allocated with malloc(). - * - * - The caller could provide storage on the stack for situations where - * that makes sense. So far that's only proved useful for - * minimask_combine(), but the principle works elsewhere. - * - * Elements in 'values' are allowed to be zero. This is useful for "struct + * Elements in values array are allowed to be zero. This is useful for "struct * minimatch", for which ensuring that the miniflow and minimask members have * same 'map' allows optimization. This allowance applies only to a miniflow * that is not a mask. That is, a minimask may NOT have zero elements in * its 'values'. */ struct miniflow { - uint64_t map; - uint32_t *values; - uint32_t inline_values[MINI_N_INLINE]; + uint64_t map:63; + uint64_t values_inline:1; + union { + uint32_t *offline_values; + uint32_t inline_values[MINI_N_INLINE]; + }; }; +static inline uint32_t *miniflow_values(struct miniflow *mf) +{ + return mf->values_inline ? mf->inline_values : mf->offline_values; +} + +static inline const uint32_t *miniflow_get_values(const struct miniflow *mf) +{ + return mf->values_inline ? mf->inline_values : mf->offline_values; +} + +static inline const uint32_t *miniflow_get_u32_values(const struct miniflow *mf) +{ + return miniflow_get_values(mf); +} + +static inline const ovs_be32 *miniflow_get_be32_values(const struct miniflow *mf) +{ + return (OVS_FORCE const ovs_be32 *)miniflow_get_values(mf); +} + /* This is useful for initializing a miniflow for a miniflow_extract() call. */ static inline void miniflow_initialize(struct miniflow *mf, uint32_t buf[FLOW_U32S]) { mf->map = 0; - mf->values = buf; + mf->values_inline = (buf == (uint32_t *)(mf + 1)); + if (!mf->values_inline) { + mf->offline_values = buf; + } } struct pkt_metadata; @@ -415,7 +432,7 @@ mf_get_next_in_map(uint64_t *fmap, uint64_t rm1bit, const uint32_t **fp, /* Iterate through all miniflow u32 values specified by the 'MAP'. * This works as the first statement in a block.*/ #define MINIFLOW_FOR_EACH_IN_MAP(VALUE, FLOW, MAP) \ - const uint32_t *fp_ = (FLOW)->values; \ + const uint32_t *fp_ = miniflow_get_u32_values(FLOW); \ uint64_t rm1bit_, fmap_, map_; \ for (fmap_ = (FLOW)->map, map_ = (MAP), rm1bit_ = rightmost_1bit(map_); \ mf_get_next_in_map(&fmap_, rm1bit_, &fp_, &(VALUE)); \ @@ -426,7 +443,7 @@ mf_get_next_in_map(uint64_t *fmap, uint64_t rm1bit, const uint32_t **fp, #define MINIFLOW_GET_TYPE(MF, TYPE, OFS) \ (((MF)->map & (UINT64_C(1) << (OFS) / 4)) \ ? ((OVS_FORCE const TYPE *) \ - ((MF)->values \ + (miniflow_get_u32_values(MF) \ + count_1bits((MF)->map & ((UINT64_C(1) << (OFS) / 4) - 1)))) \ [(OFS) % 4 / sizeof(TYPE)] \ : 0) \ @@ -485,6 +502,7 @@ static inline ovs_be64 minimask_get_metadata_mask(const struct minimask *); bool minimask_equal(const struct minimask *a, const struct minimask *b); bool minimask_has_extra(const struct minimask *, const struct minimask *); + /* Returns true if 'mask' matches every packet, false if 'mask' fixes any bits * or fields. */ static inline bool @@ -496,8 +514,6 @@ minimask_is_catchall(const struct minimask *mask) return mask->masks.map == 0; } - - /* Returns the VID within the vlan_tci member of the "struct flow" represented * by 'flow'. */ static inline uint16_t @@ -560,7 +576,7 @@ static inline void flow_union_with_miniflow(struct flow *dst, const struct miniflow *src) { uint32_t *dst_u32 = (uint32_t *) dst; - const uint32_t *p = (uint32_t *)src->values; + const uint32_t *p = miniflow_get_u32_values(src); uint64_t map; for (map = src->map; map; map = zero_rightmost_1bit(map)) { diff --git a/lib/match.c b/lib/match.c index 5bbd2f02b..308f90627 100644 --- a/lib/match.c +++ b/lib/match.c @@ -1255,8 +1255,8 @@ minimatch_matches_flow(const struct minimatch *match, const struct flow *target) { const uint32_t *target_u32 = (const uint32_t *) target; - const uint32_t *flowp = match->flow.values; - const uint32_t *maskp = match->mask.masks.values; + const uint32_t *flowp = miniflow_get_u32_values(&match->flow); + const uint32_t *maskp = miniflow_get_u32_values(&match->mask.masks); uint64_t map; for (map = match->flow.map; map; map = zero_rightmost_1bit(map)) { -- 2.43.0