This is a false positive sparse warning. I changed the flowmap_aux initializer to use designated initializer instead of an inline function and that got rid of the sparse warning.
I also separated some changes into separate patches. I’ll send a v2 soon. Jarno > On Aug 5, 2015, at 1:17 PM, Joe Stringer <[email protected]> wrote: > > With this full series applied, gcc (Debian 4.9.2-10) 4.9.2: > > ../lib/classifier-private.h:352:14: warning: crazy programmer > > I think this is actually a sparse warning, and I've seen it before but > I have no recollection how we appeased it. > > On 5 August 2015 at 10:53, Jarno Rajahalme <[email protected]> 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 <[email protected]> >> Signed-off-by: Jarno Rajahalme <[email protected]> >> --- >> lib/classifier-private.h | 116 ++++++------ >> lib/classifier.c | 158 +++++++---------- >> lib/classifier.h | 1 - >> lib/dpif-netdev.c | 93 +++------- >> lib/flow.c | 349 ++++++++++++++++-------------------- >> lib/flow.h | 448 >> +++++++++++++++++++++++++++++++---------------- >> lib/match.c | 5 +- >> 7 files changed, 600 insertions(+), 570 deletions(-) >> >> diff --git a/lib/classifier-private.h b/lib/classifier-private.h >> index cc255fe..f3b44e9 100644 >> --- a/lib/classifier-private.h >> +++ b/lib/classifier-private.h >> @@ -42,7 +42,7 @@ struct cls_subtable { >> /* These fields are accessed by readers who care about wildcarding. */ >> const tag_type tag; /* Tag generated from mask for partitioning. */ >> const uint8_t n_indices; /* How many indices to use. */ >> - const struct miniflow index_maps[CLS_MAX_INDICES + 1]; /* Stage maps. */ >> + const struct flowmap index_maps[CLS_MAX_INDICES + 1]; /* Stage maps. */ >> unsigned int trie_plen[CLS_MAX_TRIES]; /* Trie prefix length in 'mask' >> * (runtime configurable). */ >> const int ports_mask_len; >> @@ -238,16 +238,16 @@ flow_hash_in_minimask(const struct flow *flow, const >> struct minimask *mask, >> const uint64_t *mask_values = miniflow_get_values(&mask->masks); >> const uint64_t *flow_u64 = (const uint64_t *)flow; >> const uint64_t *p = mask_values; >> - uint32_t hash; >> - size_t idx; >> + uint32_t hash = basis; >> + map_t map; >> >> - hash = basis; >> - MAP_FOR_EACH_INDEX(idx, mask->masks.tnl_map) { >> - hash = hash_add64(hash, flow_u64[idx] & *p++); >> - } >> - flow_u64 += FLOW_TNL_U64S; >> - MAP_FOR_EACH_INDEX(idx, mask->masks.pkt_map) { >> - hash = hash_add64(hash, flow_u64[idx] & *p++); >> + FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) { >> + size_t idx; >> + >> + MAP_FOR_EACH_INDEX (idx, map) { >> + hash = hash_add64(hash, flow_u64[idx] & *p++); >> + } >> + flow_u64 += MAP_T_BITS; >> } >> >> return hash_finish(hash, (p - mask_values) * 8); >> @@ -265,13 +265,10 @@ miniflow_hash_in_minimask(const struct miniflow *flow, >> const uint64_t *mask_values = miniflow_get_values(&mask->masks); >> const uint64_t *p = mask_values; >> uint32_t hash = basis; >> - uint64_t flow_u64; >> + uint64_t value; >> >> - MINIFLOW_FOR_EACH_IN_TNL_MAP(flow_u64, flow, mask->masks) { >> - hash = hash_add64(hash, flow_u64 & *p++); >> - } >> - MINIFLOW_FOR_EACH_IN_PKT_MAP(flow_u64, flow, mask->masks) { >> - hash = hash_add64(hash, flow_u64 & *p++); >> + MINIFLOW_FOR_EACH_IN_FLOWMAP(value, flow, mask->masks.map) { >> + hash = hash_add64(hash, value & *p++); >> } >> >> return hash_finish(hash, (p - mask_values) * 8); >> @@ -285,24 +282,23 @@ miniflow_hash_in_minimask(const struct miniflow *flow, >> static inline uint32_t >> flow_hash_in_minimask_range(const struct flow *flow, >> const struct minimask *mask, >> - const struct miniflow *maps, >> + const struct flowmap fmap, >> unsigned int *offset, >> uint32_t *basis) >> { >> const uint64_t *mask_values = miniflow_get_values(&mask->masks); >> - const uint64_t *p = mask_values + *offset; >> const uint64_t *flow_u64 = (const uint64_t *)flow; >> + const uint64_t *p = mask_values + *offset; >> uint32_t hash = *basis; >> - size_t idx; >> + map_t map; >> >> - if (OVS_UNLIKELY(maps->tnl_map)) { >> - MAP_FOR_EACH_INDEX(idx, maps->tnl_map) { >> + FLOWMAP_FOR_EACH_MAP (map, fmap) { >> + size_t idx; >> + >> + MAP_FOR_EACH_INDEX (idx, map) { >> hash = hash_add64(hash, flow_u64[idx] & *p++); >> } >> - } >> - flow_u64 += FLOW_TNL_U64S; >> - MAP_FOR_EACH_INDEX(idx, maps->pkt_map) { >> - hash = hash_add64(hash, flow_u64[idx] & *p++); >> + flow_u64 += MAP_T_BITS; >> } >> >> *basis = hash; /* Allow continuation from the unfinished value. */ >> @@ -324,20 +320,19 @@ flow_wildcards_fold_minimask(struct flow_wildcards *wc, >> static inline void >> flow_wildcards_fold_minimask_in_map(struct flow_wildcards *wc, >> const struct minimask *mask, >> - const struct miniflow *map) >> + const struct flowmap fmap) >> { >> const uint64_t *p = miniflow_get_values(&mask->masks); >> uint64_t *dst_u64 = (uint64_t *)&wc->masks; >> - size_t idx; >> + map_t map; >> + >> + FLOWMAP_FOR_EACH_MAP (map, fmap) { >> + size_t idx; >> >> - if (map->tnl_map) { >> - MAP_FOR_EACH_INDEX(idx, map->tnl_map) { >> + MAP_FOR_EACH_INDEX (idx, map) { >> dst_u64[idx] |= *p++; >> } >> - } >> - dst_u64 += FLOW_TNL_U64S; >> - MAP_FOR_EACH_INDEX(idx, map->pkt_map) { >> - dst_u64[idx] |= *p++; >> + dst_u64 += MAP_T_BITS; >> } >> } >> >> @@ -348,25 +343,21 @@ miniflow_hash(const struct miniflow *flow, uint32_t >> basis) >> const uint64_t *values = miniflow_get_values(flow); >> const uint64_t *p = values; >> uint32_t hash = basis; >> - uint64_t hash_tnl_map = 0, hash_pkt_map = 0; >> - uint64_t map; >> + struct flowmap hash_map; >> + map_t map; >> + size_t idx; >> >> - for (map = flow->tnl_map; map; map = zero_rightmost_1bit(map)) { >> + flowmap_init(&hash_map); >> + FLOWMAP_FOR_EACH_INDEX (idx, flow->map) { >> if (*p) { >> hash = hash_add64(hash, *p); >> - hash_tnl_map |= rightmost_1bit(map); >> + flowmap_set(&hash_map, idx, 1); >> } >> p++; >> } >> - for (map = flow->pkt_map; map; map = zero_rightmost_1bit(map)) { >> - if (*p) { >> - hash = hash_add64(hash, *p); >> - hash_pkt_map |= rightmost_1bit(map); >> - } >> - p++; >> + FLOWMAP_FOR_EACH_MAP (map, hash_map) { >> + hash = hash_add64(hash, map); >> } >> - hash = hash_add64(hash, hash_tnl_map); >> - hash = hash_add64(hash, hash_pkt_map); >> >> return hash_finish(hash, p - values); >> } >> @@ -375,14 +366,20 @@ miniflow_hash(const struct miniflow *flow, uint32_t >> basis) >> static inline uint32_t >> minimask_hash(const struct minimask *mask, uint32_t basis) >> { >> - return miniflow_hash(&mask->masks, basis); >> -} >> + const uint64_t *values = miniflow_get_values(&mask->masks); >> + const uint64_t *p = values; >> + uint32_t hash = basis; >> + map_t map; >> + const uint64_t *end = values + miniflow_n_values(&mask->masks); >> >> -/* Returns a hash value for 'match', given 'basis'. */ >> -static inline uint32_t >> -minimatch_hash(const struct minimatch *match, uint32_t basis) >> -{ >> - return miniflow_hash(match->flow, minimask_hash(match->mask, basis)); >> + while (p < end) { >> + hash = hash_add64(hash, *p++); >> + } >> + FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) { >> + hash = hash_add64(hash, map); >> + } >> + >> + return hash_finish(hash, p - values); >> } >> >> /* Returns a hash value for the bits of range [start, end) in 'minimatch', >> @@ -392,20 +389,15 @@ minimatch_hash(const struct minimatch *match, uint32_t >> basis) >> * flow_hash_in_minimask_range(), only the form of the arguments differ. */ >> static inline uint32_t >> minimatch_hash_range(const struct minimatch *match, >> - const struct miniflow *maps, unsigned int *offset, >> + const struct flowmap map, unsigned int *offset, >> uint32_t *basis) >> { >> - const uint64_t *p = miniflow_get_values(match->flow); >> - const uint64_t *q = miniflow_get_values(&match->mask->masks); >> + const uint64_t *p = miniflow_get_values(match->flow) + *offset; >> + const uint64_t *q = miniflow_get_values(&match->mask->masks) + *offset; >> uint32_t hash = *basis; >> - int n, i; >> - >> - n = miniflow_n_values(maps); >> - >> - q += *offset; >> - p += *offset; >> + int n = flowmap_n_1bits(map); >> >> - for (i = 0; i < n; i++) { >> + for (int i = 0; i < n; i++) { >> hash = hash_add64(hash, p[i] & q[i]); >> } >> *basis = hash; /* Allow continuation from the unfinished value. */ >> diff --git a/lib/classifier.c b/lib/classifier.c >> index 975d04f..fb5e6e8 100644 >> --- a/lib/classifier.c >> +++ b/lib/classifier.c >> @@ -262,13 +262,6 @@ cls_rule_equal(const struct cls_rule *a, const struct >> cls_rule *b) >> return a->priority == b->priority && minimatch_equal(&a->match, >> &b->match); >> } >> >> -/* Returns a hash value for 'rule', folding in 'basis'. */ >> -uint32_t >> -cls_rule_hash(const struct cls_rule *rule, uint32_t basis) >> -{ >> - return minimatch_hash(&rule->match, hash_int(rule->priority, basis)); >> -} >> - >> /* Appends a string describing 'rule' to 's'. */ >> void >> cls_rule_format(const struct cls_rule *rule, struct ds *s) >> @@ -600,10 +593,10 @@ classifier_replace(struct classifier *cls, const >> struct cls_rule *rule, >> basis = 0; >> mask_offset = 0; >> for (i = 0; i < subtable->n_indices; i++) { >> - ihash[i] = minimatch_hash_range(&rule->match, >> &subtable->index_maps[i], >> + ihash[i] = minimatch_hash_range(&rule->match, >> subtable->index_maps[i], >> &mask_offset, &basis); >> } >> - hash = minimatch_hash_range(&rule->match, &subtable->index_maps[i], >> + hash = minimatch_hash_range(&rule->match, subtable->index_maps[i], >> &mask_offset, &basis); >> >> head = find_equal(subtable, rule->match.flow, hash); >> @@ -804,10 +797,10 @@ classifier_remove(struct classifier *cls, const struct >> cls_rule *cls_rule) >> mask_offset = 0; >> for (i = 0; i < subtable->n_indices; i++) { >> ihash[i] = minimatch_hash_range(&cls_rule->match, >> - &subtable->index_maps[i], >> + subtable->index_maps[i], >> &mask_offset, &basis); >> } >> - hash = minimatch_hash_range(&cls_rule->match, &subtable->index_maps[i], >> + hash = minimatch_hash_range(&cls_rule->match, subtable->index_maps[i], >> &mask_offset, &basis); >> >> head = find_equal(subtable, cls_rule->match.flow, hash); >> @@ -1532,40 +1525,32 @@ find_subtable(const struct classifier *cls, const >> struct minimask *mask) >> /* Initializes 'map' with a subset of 'miniflow''s maps that includes only >> the >> * portions with u64-offset 'i' such that 'start' <= i < 'end'. Does not >> copy >> * any data from 'miniflow' to 'map'. */ >> -static void >> -miniflow_get_map_in_range(const struct miniflow *miniflow, >> - uint8_t start, uint8_t end, struct miniflow *map) >> +static struct flowmap >> +miniflow_get_map_in_range(const struct miniflow *miniflow, uint8_t start, >> + uint8_t end) >> { >> - *map = *miniflow; /* Copy maps. */ >> - >> - if (start >= FLOW_TNL_U64S) { >> - map->tnl_map = 0; >> - if (start > FLOW_TNL_U64S) { >> - /* Clear 'start - FLOW_TNL_U64S' LSBs from pkt_map. */ >> - start -= FLOW_TNL_U64S; >> - uint64_t msk = (UINT64_C(1) << start) - 1; >> + struct flowmap map; >> + size_t ofs = 0; >> >> - map->pkt_map &= ~msk; >> - } >> - } else if (start > 0) { >> - /* Clear 'start' LSBs from tnl_map. */ >> - uint64_t msk = (UINT64_C(1) << start) - 1; >> + map = miniflow->map; >> >> - map->tnl_map &= ~msk; >> + /* Clear the bits before 'start'. */ >> + while (start >= MAP_T_BITS) { >> + start -= MAP_T_BITS; >> + ofs += MAP_T_BITS; >> + map.bits[start / MAP_T_BITS] = 0; >> + } >> + if (start > 0) { >> + flowmap_clear(&map, ofs, start); >> } >> >> - if (end <= FLOW_TNL_U64S) { >> - map->pkt_map = 0; >> - if (end < FLOW_TNL_U64S) { >> - /* Keep 'end' LSBs in tnl_map. */ >> - map->tnl_map &= (UINT64_C(1) << end) - 1; >> - } >> - } else { >> - if (end < FLOW_U64S) { >> - /* Keep 'end - FLOW_TNL_U64S' LSBs in pkt_map. */ >> - map->pkt_map &= (UINT64_C(1) << (end - FLOW_TNL_U64S)) - 1; >> - } >> + /* Clear the bits starting at 'end'. */ >> + if (end < FLOW_U64S) { >> + /* flowmap_clear() can handle at most MAP_T_BITS at a time. */ >> + ovs_assert(FLOW_U64S - end <= MAP_T_BITS); >> + flowmap_clear(&map, end, FLOW_U64S - end); >> } >> + return map; >> } >> >> /* The new subtable will be visible to the readers only after this. */ >> @@ -1575,7 +1560,7 @@ insert_subtable(struct classifier *cls, const struct >> minimask *mask) >> uint32_t hash = minimask_hash(mask, 0); >> struct cls_subtable *subtable; >> int i, index = 0; >> - struct minimask stage_mask; >> + struct flowmap stage_map; >> uint8_t prev; >> size_t count = miniflow_n_values(&mask->masks); >> >> @@ -1587,26 +1572,25 @@ insert_subtable(struct classifier *cls, const struct >> minimask *mask) >> /* Init indices for segmented lookup, if any. */ >> prev = 0; >> for (i = 0; i < cls->n_flow_segments; i++) { >> - miniflow_get_map_in_range(&mask->masks, prev, cls->flow_segments[i], >> - &stage_mask.masks); >> + stage_map = miniflow_get_map_in_range(&mask->masks, prev, >> + cls->flow_segments[i]); >> /* Add an index if it adds mask bits. */ >> - if (!minimask_is_catchall(&stage_mask)) { >> + if (!flowmap_is_empty(stage_map)) { >> cmap_init(&subtable->indices[index]); >> - *CONST_CAST(struct miniflow *, &subtable->index_maps[index]) >> - = stage_mask.masks; >> + *CONST_CAST(struct flowmap *, &subtable->index_maps[index]) >> + = stage_map; >> index++; >> } >> prev = cls->flow_segments[i]; >> } >> /* Map for the final stage. */ >> - miniflow_get_map_in_range( >> - &mask->masks, prev, FLOW_U64S, >> - CONST_CAST(struct miniflow *, &subtable->index_maps[index])); >> + *CONST_CAST(struct flowmap *, &subtable->index_maps[index]) >> + = miniflow_get_map_in_range(&mask->masks, prev, FLOW_U64S); >> /* Check if the final stage adds any bits, >> * and remove the last index if it doesn't. */ >> if (index > 0) { >> - if (miniflow_equal_maps(&subtable->index_maps[index], >> - &subtable->index_maps[index - 1])) { >> + if (flowmap_equal(subtable->index_maps[index], >> + subtable->index_maps[index - 1])) { >> --index; >> cmap_destroy(&subtable->indices[index]); >> } >> @@ -1665,7 +1649,7 @@ static unsigned int be_get_bit_at(const ovs_be32 >> value[], unsigned int ofs); >> static inline bool >> check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries, >> const unsigned int field_plen[CLS_MAX_TRIES], >> - const struct miniflow *range_map, const struct flow *flow, >> + const struct flowmap range_map, const struct flow *flow, >> struct flow_wildcards *wc) >> { >> int j; >> @@ -1681,7 +1665,7 @@ check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], >> unsigned int n_tries, >> uint8_t be64ofs = be32ofs / 2; >> >> /* Is the trie field within the current range of fields? */ >> - if (MINIFLOW_IN_MAP(range_map, be64ofs)) { >> + if (FLOWMAP_IS_SET(range_map, be64ofs)) { >> /* On-demand trie lookup. */ >> if (!ctx->lookup_done) { >> memset(&ctx->match_plens, 0, sizeof ctx->match_plens); >> @@ -1736,20 +1720,18 @@ miniflow_and_mask_matches_flow(const struct miniflow >> *flow, >> const uint64_t *flowp = miniflow_get_values(flow); >> const uint64_t *maskp = miniflow_get_values(&mask->masks); >> const uint64_t *target_u64 = (const uint64_t *)target; >> - size_t idx; >> + map_t map; >> >> - MAP_FOR_EACH_INDEX(idx, mask->masks.tnl_map) { >> - if ((*flowp++ ^ target_u64[idx]) & *maskp++) { >> - return false; >> - } >> - } >> - target_u64 += FLOW_TNL_U64S; >> - MAP_FOR_EACH_INDEX(idx, mask->masks.pkt_map) { >> - if ((*flowp++ ^ target_u64[idx]) & *maskp++) { >> - return false; >> + FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) { >> + size_t idx; >> + >> + MAP_FOR_EACH_INDEX (idx, map) { >> + if ((*flowp++ ^ target_u64[idx]) & *maskp++) { >> + return false; >> + } >> } >> + target_u64 += MAP_T_BITS; >> } >> - >> return true; >> } >> >> @@ -1792,33 +1774,24 @@ miniflow_and_mask_matches_flow_wc(const struct >> miniflow *flow, >> const uint64_t *target_u64 = (const uint64_t *)target; >> uint64_t *wc_u64 = (uint64_t *)&wc->masks; >> uint64_t diff; >> + map_t map; >> size_t idx; >> >> - MAP_FOR_EACH_INDEX(idx, mask->masks.tnl_map) { >> - uint64_t msk = *maskp++; >> + FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) { >> + MAP_FOR_EACH_INDEX(idx, map) { >> + uint64_t msk = *maskp++; >> >> - diff = (*flowp++ ^ target_u64[idx]) & msk; >> - if (diff) { >> - goto out; >> - } >> - >> - /* Fill in the bits that were looked at. */ >> - wc_u64[idx] |= msk; >> - } >> - target_u64 += FLOW_TNL_U64S; >> - wc_u64 += FLOW_TNL_U64S; >> - MAP_FOR_EACH_INDEX(idx, mask->masks.pkt_map) { >> - uint64_t msk = *maskp++; >> + diff = (*flowp++ ^ target_u64[idx]) & msk; >> + if (diff) { >> + goto out; >> + } >> >> - diff = (*flowp++ ^ target_u64[idx]) & msk; >> - if (diff) { >> - goto out; >> + /* Fill in the bits that were looked at. */ >> + wc_u64[idx] |= msk; >> } >> - >> - /* Fill in the bits that were looked at. */ >> - wc_u64[idx] |= msk; >> + target_u64 += MAP_T_BITS; >> + wc_u64 += MAP_T_BITS; >> } >> - >> return true; >> >> out: >> @@ -1840,7 +1813,7 @@ find_match_wc(const struct cls_subtable *subtable, >> cls_version_t version, >> uint32_t basis = 0, hash; >> const struct cls_match *rule = NULL; >> int i; >> - struct miniflow stages_map; >> + struct flowmap stages_map; >> unsigned int mask_offset = 0; >> >> if (OVS_UNLIKELY(!wc)) { >> @@ -1848,24 +1821,23 @@ find_match_wc(const struct cls_subtable *subtable, >> cls_version_t version, >> flow_hash_in_minimask(flow, &subtable->mask, 0)); >> } >> >> - memset(&stages_map, 0, sizeof stages_map); >> + flowmap_init(&stages_map); >> /* Try to finish early by checking fields in segments. */ >> for (i = 0; i < subtable->n_indices; i++) { >> const struct cmap_node *inode; >> >> if (check_tries(trie_ctx, n_tries, subtable->trie_plen, >> - &subtable->index_maps[i], flow, wc)) { >> + subtable->index_maps[i], flow, wc)) { >> /* 'wc' bits for the trie field set, now unwildcard the preceding >> * bits used so far. */ >> goto no_match; >> } >> >> /* Accumulate the map used so far. */ >> - stages_map.tnl_map |= subtable->index_maps[i].tnl_map; >> - stages_map.pkt_map |= subtable->index_maps[i].pkt_map; >> + stages_map = flowmap_or(stages_map, subtable->index_maps[i]); >> >> hash = flow_hash_in_minimask_range(flow, &subtable->mask, >> - &subtable->index_maps[i], >> + subtable->index_maps[i], >> &mask_offset, &basis); >> >> inode = cmap_find(&subtable->indices[i], hash); >> @@ -1897,11 +1869,11 @@ find_match_wc(const struct cls_subtable *subtable, >> cls_version_t version, >> } >> /* Trie check for the final range. */ >> if (check_tries(trie_ctx, n_tries, subtable->trie_plen, >> - &subtable->index_maps[i], flow, wc)) { >> + subtable->index_maps[i], flow, wc)) { >> goto no_match; >> } >> hash = flow_hash_in_minimask_range(flow, &subtable->mask, >> - &subtable->index_maps[i], >> + subtable->index_maps[i], >> &mask_offset, &basis); >> rule = find_match(subtable, version, flow, hash); >> if (!rule && subtable->ports_mask_len) { >> @@ -1928,7 +1900,7 @@ find_match_wc(const struct cls_subtable *subtable, >> cls_version_t version, >> no_match: >> /* Unwildcard the bits in stages so far, as they were used in determining >> * there is no match. */ >> - flow_wildcards_fold_minimask_in_map(wc, &subtable->mask, &stages_map); >> + flow_wildcards_fold_minimask_in_map(wc, &subtable->mask, stages_map); >> return NULL; >> } >> >> diff --git a/lib/classifier.h b/lib/classifier.h >> index 5ffe756..889dc1e 100644 >> --- a/lib/classifier.h >> +++ b/lib/classifier.h >> @@ -372,7 +372,6 @@ void cls_rule_set_conjunctions(struct cls_rule *, >> const struct cls_conjunction *, size_t n); >> >> bool cls_rule_equal(const struct cls_rule *, const struct cls_rule *); >> -uint32_t cls_rule_hash(const struct cls_rule *, uint32_t basis); >> void cls_rule_format(const struct cls_rule *, struct ds *); >> bool cls_rule_is_catchall(const struct cls_rule *); >> bool cls_rule_is_loose_match(const struct cls_rule *rule, >> diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c >> index 83e55e7..357b750 100644 >> --- a/lib/dpif-netdev.c >> +++ b/lib/dpif-netdev.c >> @@ -488,15 +488,12 @@ emc_cache_init(struct emc_cache *flow_cache) >> { >> int i; >> >> - BUILD_ASSERT(sizeof(struct miniflow) == 2 * sizeof(uint64_t)); >> - >> flow_cache->sweep_idx = 0; >> for (i = 0; i < ARRAY_SIZE(flow_cache->entries); i++) { >> flow_cache->entries[i].flow = NULL; >> flow_cache->entries[i].key.hash = 0; >> flow_cache->entries[i].key.len = sizeof(struct miniflow); >> - flow_cache->entries[i].key.mf.tnl_map = 0; >> - flow_cache->entries[i].key.mf.pkt_map = 0; >> + flowmap_init(&flow_cache->entries[i].key.mf.map); >> } >> } >> >> @@ -1521,12 +1518,7 @@ static bool dp_netdev_flow_ref(struct dp_netdev_flow >> *flow) >> * miniflow_extract(), if the map is different the miniflow is different. >> * Therefore we can be faster by comparing the map and the miniflow in a >> * single memcmp(). >> - * - These functions can be inlined by the compiler. >> - * >> - * The following assertions make sure that what we're doing with miniflow is >> - * safe. >> - */ >> -BUILD_ASSERT_DECL(sizeof(struct miniflow) == 2 * sizeof(uint64_t)); >> + * - These functions can be inlined by the compiler. */ >> >> /* Given the number of bits set in miniflow's maps, returns the size of the >> * 'netdev_flow_key.mf' */ >> @@ -1585,47 +1577,32 @@ static inline void >> netdev_flow_mask_init(struct netdev_flow_key *mask, >> const struct match *match) >> { >> - const uint64_t *mask_u64 = (const uint64_t *) &match->wc.masks; >> uint64_t *dst = miniflow_values(&mask->mf); >> - struct miniflow maps; >> - uint64_t map; >> + struct flowmap fmap; >> uint32_t hash = 0; >> - int n; >> + size_t idx; >> >> /* Only check masks that make sense for the flow. */ >> - flow_wc_map(&match->flow, &maps); >> - memset(&mask->mf, 0, sizeof mask->mf); /* Clear maps. */ >> + flow_wc_map(&match->flow, &fmap); >> + flowmap_init(&mask->mf.map); >> >> - map = maps.tnl_map; >> - while (map) { >> - uint64_t rm1bit = rightmost_1bit(map); >> - int i = raw_ctz(map); >> + FLOWMAP_FOR_EACH_INDEX(idx, fmap) { >> + uint64_t mask_u64 = flow_u64_value(&match->wc.masks, idx); >> >> - if (mask_u64[i]) { >> - mask->mf.tnl_map |= rm1bit; >> - *dst++ = mask_u64[i]; >> - hash = hash_add64(hash, mask_u64[i]); >> + if (mask_u64) { >> + flowmap_set(&mask->mf.map, idx, 1); >> + *dst++ = mask_u64; >> + hash = hash_add64(hash, mask_u64); >> } >> - map -= rm1bit; >> } >> - mask_u64 += FLOW_TNL_U64S; >> - map = maps.pkt_map; >> - while (map) { >> - uint64_t rm1bit = rightmost_1bit(map); >> - int i = raw_ctz(map); >> >> - if (mask_u64[i]) { >> - mask->mf.pkt_map |= rm1bit; >> - *dst++ = mask_u64[i]; >> - hash = hash_add64(hash, mask_u64[i]); >> - } >> - map -= rm1bit; >> - } >> + map_t map; >> >> - hash = hash_add64(hash, mask->mf.tnl_map); >> - hash = hash_add64(hash, mask->mf.pkt_map); >> + FLOWMAP_FOR_EACH_MAP (map, mask->mf.map) { >> + hash = hash_add64(hash, map); >> + } >> >> - n = dst - miniflow_get_values(&mask->mf); >> + size_t n = dst - miniflow_get_values(&mask->mf); >> >> mask->hash = hash_finish(hash, n * 8); >> mask->len = netdev_flow_key_size(n); >> @@ -1645,7 +1622,7 @@ netdev_flow_key_init_masked(struct netdev_flow_key >> *dst, >> dst->len = mask->len; >> dst->mf = mask->mf; /* Copy maps. */ >> >> - FLOW_FOR_EACH_IN_MAPS(value, flow, mask->mf) { >> + FLOW_FOR_EACH_IN_MAPS(value, flow, mask->mf.map) { >> *dst_u64 = value & *mask_u64++; >> hash = hash_add64(hash, *dst_u64++); >> } >> @@ -1653,13 +1630,9 @@ netdev_flow_key_init_masked(struct netdev_flow_key >> *dst, >> (dst_u64 - miniflow_get_values(&dst->mf)) * 8); >> } >> >> -/* Iterate through netdev_flow_key TNL u64 values specified by 'MAPS'. */ >> -#define NETDEV_FLOW_KEY_FOR_EACH_IN_TNL_MAP(VALUE, KEY, MAPS) \ >> - MINIFLOW_FOR_EACH_IN_TNL_MAP(VALUE, &(KEY)->mf, MAPS) >> - >> -/* Iterate through netdev_flow_key PKT u64 values specified by 'MAPS'. */ >> -#define NETDEV_FLOW_KEY_FOR_EACH_IN_PKT_MAP(VALUE, KEY, MAPS) \ >> - MINIFLOW_FOR_EACH_IN_PKT_MAP(VALUE, &(KEY)->mf, MAPS) >> +/* Iterate through netdev_flow_key TNL u64 values specified by 'FLOWMAP'. */ >> +#define NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(VALUE, KEY, FLOWMAP) \ >> + MINIFLOW_FOR_EACH_IN_FLOWMAP(VALUE, &(KEY)->mf, FLOWMAP) >> >> /* Returns a hash value for the bits of 'key' where there are 1-bits in >> * 'mask'. */ >> @@ -1669,13 +1642,10 @@ netdev_flow_key_hash_in_mask(const struct >> netdev_flow_key *key, >> { >> const uint64_t *p = miniflow_get_values(&mask->mf); >> uint32_t hash = 0; >> - uint64_t key_u64; >> + uint64_t value; >> >> - NETDEV_FLOW_KEY_FOR_EACH_IN_TNL_MAP(key_u64, key, mask->mf) { >> - hash = hash_add64(hash, key_u64 & *p++); >> - } >> - NETDEV_FLOW_KEY_FOR_EACH_IN_PKT_MAP(key_u64, key, mask->mf) { >> - hash = hash_add64(hash, key_u64 & *p++); >> + NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(value, key, mask->mf.map) { >> + hash = hash_add64(hash, value & *p++); >> } >> >> return hash_finish(hash, (p - miniflow_get_values(&mask->mf)) * 8); >> @@ -2008,8 +1978,8 @@ dp_netdev_flow_add(struct dp_netdev_pmd_thread *pmd, >> >> netdev_flow_mask_init(&mask, match); >> /* Make sure wc does not have metadata. */ >> - ovs_assert(!(mask.mf.pkt_map >> - & (MINIFLOW_PKT_MAP(metadata) | MINIFLOW_PKT_MAP(regs)))); >> + ovs_assert(!FLOWMAP_HAS_FIELD(&mask.mf.map, metadata) >> + && !FLOWMAP_HAS_FIELD(&mask.mf.map, regs)); >> >> /* Do not allocate extra space. */ >> flow = xmalloc(sizeof *flow - sizeof flow->cr.flow.mf + mask.len); >> @@ -3886,15 +3856,10 @@ dpcls_rule_matches_key(const struct dpcls_rule *rule, >> { >> const uint64_t *keyp = miniflow_get_values(&rule->flow.mf); >> const uint64_t *maskp = miniflow_get_values(&rule->mask->mf); >> - uint64_t target_u64; >> + uint64_t value; >> >> - NETDEV_FLOW_KEY_FOR_EACH_IN_TNL_MAP(target_u64, target, rule->flow.mf) { >> - if (OVS_UNLIKELY((target_u64 & *maskp++) != *keyp++)) { >> - return false; >> - } >> - } >> - NETDEV_FLOW_KEY_FOR_EACH_IN_PKT_MAP(target_u64, target, rule->flow.mf) { >> - if (OVS_UNLIKELY((target_u64 & *maskp++) != *keyp++)) { >> + NETDEV_FLOW_KEY_FOR_EACH_IN_FLOWMAP(value, target, rule->flow.mf.map) { >> + if (OVS_UNLIKELY((value & *maskp++) != *keyp++)) { >> return false; >> } >> } >> diff --git a/lib/flow.c b/lib/flow.c >> index 9a2bb6b..091282e 100644 >> --- a/lib/flow.c >> +++ b/lib/flow.c >> @@ -112,7 +112,7 @@ data_try_pull(const void **datap, size_t *sizep, size_t >> size) >> >> /* Context for pushing data to a miniflow. */ >> struct mf_ctx { >> - struct miniflow maps; >> + struct flowmap map; >> uint64_t *data; >> uint64_t * const end; >> }; >> @@ -132,114 +132,93 @@ BUILD_MESSAGE("FLOW_WC_SEQ changed: >> miniflow_extract() will have runtime " >> #define MINIFLOW_ASSERT(X) >> #endif >> >> -#define miniflow_set_map(MF, OFS) \ >> +/* True if 'IDX' and higher bits are not set. */ >> +#define ASSERT_FLOWMAP_NOT_SET(FM, IDX) \ >> { \ >> - size_t ofs = (OFS); \ >> - \ >> - if (ofs < FLOW_TNL_U64S) { \ >> - MINIFLOW_ASSERT(!(MF.maps.tnl_map & (UINT64_MAX << ofs)) \ >> - && !MF.maps.pkt_map); \ >> - MF.maps.tnl_map |= UINT64_C(1) << ofs; \ >> - } else { \ >> - ofs -= FLOW_TNL_U64S; \ >> - MINIFLOW_ASSERT(!(MF.maps.pkt_map & (UINT64_MAX << ofs))); \ >> - MF.maps.pkt_map |= UINT64_C(1) << ofs; \ >> + MINIFLOW_ASSERT(!((FM)->bits[(IDX) / MAP_T_BITS] & \ >> + (FLOWMAP_MAX << ((IDX) % MAP_T_BITS)))); \ >> + for (size_t i = (IDX) / MAP_T_BITS + 1; i < FLOWMAP_UNITS; i++) { \ >> + MINIFLOW_ASSERT(!(FM)->bits[i]); \ >> } \ >> } >> >> -#define miniflow_assert_in_map(MF, OFS) \ >> -{ \ >> - size_t ofs = (OFS); \ >> - \ >> - if (ofs < FLOW_TNL_U64S) { \ >> - MINIFLOW_ASSERT(MF.maps.tnl_map & UINT64_C(1) << ofs \ >> - && !(MF.maps.tnl_map & UINT64_MAX << (ofs + 1)) \ >> - && !MF.maps.pkt_map); \ >> - } else { \ >> - ofs -= FLOW_TNL_U64S; \ >> - MINIFLOW_ASSERT(MF.maps.pkt_map & UINT64_C(1) << ofs \ >> - && !(MF.maps.pkt_map & UINT64_MAX << (ofs + 1))); \ >> - } \ >> +#define miniflow_set_map(MF, OFS) \ >> + { \ >> + ASSERT_FLOWMAP_NOT_SET(&MF.map, (OFS)); \ >> + flowmap_set(&MF.map, (OFS), 1); \ >> } >> >> -#define miniflow_push_uint64_(MF, OFS, VALUE) \ >> -{ \ >> - MINIFLOW_ASSERT(MF.data < MF.end && (OFS) % 8 == 0); \ >> - *MF.data++ = VALUE; \ >> - miniflow_set_map(MF, OFS / 8); >> \ >> +#define miniflow_assert_in_map(MF, OFS) \ >> + MINIFLOW_ASSERT(FLOWMAP_IS_SET(MF.map, (OFS))); \ >> + ASSERT_FLOWMAP_NOT_SET(&MF.map, (OFS) + 1) >> + >> +#define miniflow_push_uint64_(MF, OFS, VALUE) \ >> +{ \ >> + MINIFLOW_ASSERT(MF.data < MF.end && (OFS) % 8 == 0); \ >> + *MF.data++ = VALUE; \ >> + miniflow_set_map(MF, OFS / 8); \ >> } >> >> -#define miniflow_push_be64_(MF, OFS, VALUE) \ >> +#define miniflow_push_be64_(MF, OFS, VALUE) \ >> miniflow_push_uint64_(MF, OFS, (OVS_FORCE uint64_t)(VALUE)) >> >> -#define miniflow_push_uint32_(MF, OFS, VALUE) \ >> - { \ >> - MINIFLOW_ASSERT(MF.data < MF.end); \ >> - \ >> - if ((OFS) % 8 == 0) { \ >> - miniflow_set_map(MF, OFS / 8); \ >> - *(uint32_t *)MF.data = VALUE; \ >> - } else if ((OFS) % 8 == 4) { \ >> - miniflow_assert_in_map(MF, OFS / 8); \ >> - *((uint32_t *)MF.data + 1) = VALUE; \ >> - MF.data++; \ >> - } \ >> +#define miniflow_push_uint32_(MF, OFS, VALUE) \ >> + { \ >> + MINIFLOW_ASSERT(MF.data < MF.end); \ >> + \ >> + if ((OFS) % 8 == 0) { \ >> + miniflow_set_map(MF, OFS / 8); \ >> + *(uint32_t *)MF.data = VALUE; \ >> + } else if ((OFS) % 8 == 4) { \ >> + miniflow_assert_in_map(MF, OFS / 8); \ >> + *((uint32_t *)MF.data + 1) = VALUE; \ >> + MF.data++; \ >> + } \ >> } >> >> #define miniflow_push_be32_(MF, OFS, VALUE) \ >> miniflow_push_uint32_(MF, OFS, (OVS_FORCE uint32_t)(VALUE)) >> >> -#define miniflow_push_uint16_(MF, OFS, VALUE) \ >> -{ \ >> - MINIFLOW_ASSERT(MF.data < MF.end); \ >> - \ >> - if ((OFS) % 8 == 0) { \ >> - miniflow_set_map(MF, OFS / 8); \ >> - *(uint16_t *)MF.data = VALUE; \ >> - } else if ((OFS) % 8 == 2) { \ >> - miniflow_assert_in_map(MF, OFS / 8); \ >> - *((uint16_t *)MF.data + 1) = VALUE; \ >> - } else if ((OFS) % 8 == 4) { \ >> - miniflow_assert_in_map(MF, OFS / 8); \ >> - *((uint16_t *)MF.data + 2) = VALUE; \ >> - } else if ((OFS) % 8 == 6) { \ >> - miniflow_assert_in_map(MF, OFS / 8); \ >> - *((uint16_t *)MF.data + 3) = VALUE; \ >> - MF.data++; \ >> - } \ >> -} >> - >> -#define miniflow_pad_to_64_(MF, OFS) \ >> -{ \ >> - MINIFLOW_ASSERT((OFS) % 8 != 0); \ >> - miniflow_assert_in_map(MF, OFS / 8); \ >> - \ >> - memset((uint8_t *)MF.data + (OFS) % 8, 0, 8 - (OFS) % 8); \ >> - MF.data++; \ >> +#define miniflow_push_uint16_(MF, OFS, VALUE) \ >> +{ \ >> + MINIFLOW_ASSERT(MF.data < MF.end); \ >> + \ >> + if ((OFS) % 8 == 0) { \ >> + miniflow_set_map(MF, OFS / 8); \ >> + *(uint16_t *)MF.data = VALUE; \ >> + } else if ((OFS) % 8 == 2) { \ >> + miniflow_assert_in_map(MF, OFS / 8); \ >> + *((uint16_t *)MF.data + 1) = VALUE; \ >> + } else if ((OFS) % 8 == 4) { \ >> + miniflow_assert_in_map(MF, OFS / 8); \ >> + *((uint16_t *)MF.data + 2) = VALUE; \ >> + } else if ((OFS) % 8 == 6) { \ >> + miniflow_assert_in_map(MF, OFS / 8); \ >> + *((uint16_t *)MF.data + 3) = VALUE; \ >> + MF.data++; \ >> + } \ >> +} >> + >> +#define miniflow_pad_to_64_(MF, OFS) \ >> +{ \ >> + MINIFLOW_ASSERT((OFS) % 8 != 0); \ >> + miniflow_assert_in_map(MF, OFS / 8); \ >> + \ >> + memset((uint8_t *)MF.data + (OFS) % 8, 0, 8 - (OFS) % 8); \ >> + MF.data++; \ >> } >> >> #define miniflow_push_be16_(MF, OFS, VALUE) \ >> miniflow_push_uint16_(MF, OFS, (OVS_FORCE uint16_t)VALUE); >> >> -#define miniflow_set_maps(MF, OFS, N_WORDS) \ >> -{ \ >> - size_t ofs = (OFS); \ >> - size_t n_words = (N_WORDS); \ >> - uint64_t n_words_mask = UINT64_MAX >> (64 - n_words); \ >> - \ >> - MINIFLOW_ASSERT(n_words && MF.data + n_words <= MF.end); \ >> - if (ofs < FLOW_TNL_U64S) { \ >> - MINIFLOW_ASSERT(!(MF.maps.tnl_map & UINT64_MAX << ofs) \ >> - && !MF.maps.pkt_map); \ >> - MF.maps.tnl_map |= n_words_mask << ofs; \ >> - if (n_words > FLOW_TNL_U64S - ofs) { \ >> - MF.maps.pkt_map |= n_words_mask >> (FLOW_TNL_U64S - ofs); \ >> - } \ >> - } else { \ >> - ofs -= FLOW_TNL_U64S; \ >> - MINIFLOW_ASSERT(!(MF.maps.pkt_map & (UINT64_MAX << ofs))); \ >> - MF.maps.pkt_map |= n_words_mask << ofs; \ >> - } \ >> +#define miniflow_set_maps(MF, OFS, N_WORDS) \ >> +{ \ >> + size_t ofs = (OFS); \ >> + size_t n_words = (N_WORDS); \ >> + \ >> + MINIFLOW_ASSERT(n_words && MF.data + n_words <= MF.end); \ >> + ASSERT_FLOWMAP_NOT_SET(&MF.map, ofs); \ >> + flowmap_set(&MF.map, ofs, n_words); \ >> } >> >> /* Data at 'valuep' may be unaligned. */ >> @@ -461,7 +440,8 @@ miniflow_extract(struct dp_packet *packet, struct >> miniflow *dst) >> const void *data = dp_packet_data(packet); >> size_t size = dp_packet_size(packet); >> uint64_t *values = miniflow_values(dst); >> - struct mf_ctx mf = { { 0, 0 }, values, values + FLOW_U64S }; >> + struct mf_ctx mf = { FLOWMAP_EMPTY_INITIALIZER, values, >> + values + FLOW_U64S }; >> const char *l2; >> ovs_be16 dl_type; >> uint8_t nw_frag, nw_tos, nw_ttl, nw_proto; >> @@ -767,7 +747,7 @@ miniflow_extract(struct dp_packet *packet, struct >> miniflow *dst) >> } >> } >> out: >> - *dst = mf.maps; >> + dst->map = mf.map; >> } >> >> /* For every bit of a field that is wildcarded in 'wildcards', sets the >> @@ -1255,56 +1235,74 @@ void flow_wildcards_init_for_packet(struct >> flow_wildcards *wc, >> * >> * This is a less precise version of flow_wildcards_init_for_packet() above. >> */ >> void >> -flow_wc_map(const struct flow *flow, struct miniflow *map) >> +flow_wc_map(const struct flow *flow, struct flowmap *map) >> { >> /* Update this function whenever struct flow changes. */ >> BUILD_ASSERT_DECL(FLOW_WC_SEQ == 33); >> >> - map->tnl_map = 0; >> + flowmap_init(map); >> + >> if (flow->tunnel.ip_dst) { >> - map->tnl_map = MINIFLOW_TNL_MAP(tunnel); >> + FLOWMAP_SET(map, tunnel); >> if (!flow->tunnel.metadata.opt_map) { >> - map->tnl_map &= ~MINIFLOW_TNL_MAP(tunnel.metadata); >> + FLOWMAP_CLEAR(map, tunnel.metadata); >> } >> } >> >> /* Metadata fields that can appear on packet input. */ >> - map->pkt_map = MINIFLOW_PKT_MAP(skb_priority) | >> MINIFLOW_PKT_MAP(pkt_mark) >> - | MINIFLOW_PKT_MAP(recirc_id) | MINIFLOW_PKT_MAP(dp_hash) >> - | MINIFLOW_PKT_MAP(in_port) >> - | MINIFLOW_PKT_MAP(dl_dst) | MINIFLOW_PKT_MAP(dl_src) >> - | MINIFLOW_PKT_MAP(dl_type) | MINIFLOW_PKT_MAP(vlan_tci); >> + FLOWMAP_SET(map, skb_priority); >> + FLOWMAP_SET(map, pkt_mark); >> + FLOWMAP_SET(map, recirc_id); >> + FLOWMAP_SET(map, dp_hash); >> + FLOWMAP_SET(map, in_port); >> + FLOWMAP_SET(map, dl_dst); >> + FLOWMAP_SET(map, dl_src); >> + FLOWMAP_SET(map, dl_type); >> + FLOWMAP_SET(map, vlan_tci); >> >> /* Ethertype-dependent fields. */ >> if (OVS_LIKELY(flow->dl_type == htons(ETH_TYPE_IP))) { >> - map->pkt_map |= MINIFLOW_PKT_MAP(nw_src) | MINIFLOW_PKT_MAP(nw_dst) >> - | MINIFLOW_PKT_MAP(nw_proto) | MINIFLOW_PKT_MAP(nw_frag) >> - | MINIFLOW_PKT_MAP(nw_tos) | MINIFLOW_PKT_MAP(nw_ttl); >> + FLOWMAP_SET(map, nw_src); >> + FLOWMAP_SET(map, nw_dst); >> + FLOWMAP_SET(map, nw_proto); >> + FLOWMAP_SET(map, nw_frag); >> + FLOWMAP_SET(map, nw_tos); >> + FLOWMAP_SET(map, nw_ttl); >> + >> if (OVS_UNLIKELY(flow->nw_proto == IPPROTO_IGMP)) { >> - map->pkt_map |= MINIFLOW_PKT_MAP(igmp_group_ip4); >> + FLOWMAP_SET(map, igmp_group_ip4); >> } else { >> - map->pkt_map |= MINIFLOW_PKT_MAP(tcp_flags) >> - | MINIFLOW_PKT_MAP(tp_src) | MINIFLOW_PKT_MAP(tp_dst); >> + FLOWMAP_SET(map, tcp_flags); >> + FLOWMAP_SET(map, tp_src); >> + FLOWMAP_SET(map, tp_dst); >> } >> } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) { >> - map->pkt_map |= MINIFLOW_PKT_MAP(ipv6_src) | >> MINIFLOW_PKT_MAP(ipv6_dst) >> - | MINIFLOW_PKT_MAP(ipv6_label) >> - | MINIFLOW_PKT_MAP(nw_proto) | MINIFLOW_PKT_MAP(nw_frag) >> - | MINIFLOW_PKT_MAP(nw_tos) | MINIFLOW_PKT_MAP(nw_ttl); >> + FLOWMAP_SET(map, ipv6_src); >> + FLOWMAP_SET(map, ipv6_dst); >> + FLOWMAP_SET(map, ipv6_label); >> + FLOWMAP_SET(map, nw_proto); >> + FLOWMAP_SET(map, nw_frag); >> + FLOWMAP_SET(map, nw_tos); >> + FLOWMAP_SET(map, nw_ttl); >> + >> if (OVS_UNLIKELY(flow->nw_proto == IPPROTO_ICMPV6)) { >> - map->pkt_map |= MINIFLOW_PKT_MAP(nd_target) >> - | MINIFLOW_PKT_MAP(arp_sha) | MINIFLOW_PKT_MAP(arp_tha); >> + FLOWMAP_SET(map, nd_target); >> + FLOWMAP_SET(map, arp_sha); >> + FLOWMAP_SET(map, arp_tha); >> } else { >> - map->pkt_map |= MINIFLOW_PKT_MAP(tcp_flags) >> - | MINIFLOW_PKT_MAP(tp_src) | MINIFLOW_PKT_MAP(tp_dst); >> + FLOWMAP_SET(map, tcp_flags); >> + FLOWMAP_SET(map, tp_src); >> + FLOWMAP_SET(map, tp_dst); >> } >> } else if (eth_type_mpls(flow->dl_type)) { >> - map->pkt_map |= MINIFLOW_PKT_MAP(mpls_lse); >> + FLOWMAP_SET(map, mpls_lse); >> } else if (flow->dl_type == htons(ETH_TYPE_ARP) || >> flow->dl_type == htons(ETH_TYPE_RARP)) { >> - map->pkt_map |= MINIFLOW_PKT_MAP(nw_src) | MINIFLOW_PKT_MAP(nw_dst) >> - | MINIFLOW_PKT_MAP(nw_proto) >> - | MINIFLOW_PKT_MAP(arp_sha) | MINIFLOW_PKT_MAP(arp_tha); >> + FLOWMAP_SET(map, nw_src); >> + FLOWMAP_SET(map, nw_dst); >> + FLOWMAP_SET(map, nw_proto); >> + FLOWMAP_SET(map, arp_sha); >> + FLOWMAP_SET(map, arp_tha); >> } >> } >> >> @@ -1458,11 +1456,14 @@ miniflow_hash_5tuple(const struct miniflow *flow, >> uint32_t basis) >> >> /* Separate loops for better optimization. */ >> if (dl_type == htons(ETH_TYPE_IPV6)) { >> - struct miniflow maps = { 0, MINIFLOW_PKT_MAP(ipv6_src) >> - | MINIFLOW_PKT_MAP(ipv6_dst) }; >> + struct flowmap map; >> uint64_t value; >> >> - MINIFLOW_FOR_EACH_IN_PKT_MAP(value, flow, maps) { >> + flowmap_init(&map); >> + FLOWMAP_SET(&map, ipv6_src); >> + FLOWMAP_SET(&map, ipv6_dst); >> + >> + MINIFLOW_FOR_EACH_IN_FLOWMAP(value, flow, map) { >> hash = hash_add64(hash, value); >> } >> } else { >> @@ -2212,9 +2213,8 @@ flow_compose(struct dp_packet *p, const struct flow >> *flow) >> /* Compressed flow. */ >> >> /* Completes an initialization of 'dst' as a miniflow copy of 'src' begun by >> - * the caller. The caller must have already computed 'dst->tnl_map' and >> - * 'dst->pkt_map' properly to indicate the significant uint64_t elements of >> - * 'src'. >> + * 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, >> @@ -2222,12 +2222,11 @@ flow_compose(struct dp_packet *p, const struct flow >> *flow) >> void >> miniflow_init(struct miniflow *dst, const struct flow *src) >> { >> - const uint64_t *src_u64 = (const uint64_t *) src; >> uint64_t *dst_u64 = miniflow_values(dst); >> size_t idx; >> >> - MAPS_FOR_EACH_INDEX(idx, *dst) { >> - *dst_u64++ = src_u64[idx]; >> + FLOWMAP_FOR_EACH_INDEX(idx, dst->map) { >> + *dst_u64++ = flow_u64_value(src, idx); >> } >> } >> >> @@ -2235,21 +2234,11 @@ miniflow_init(struct miniflow *dst, const struct >> flow *src) >> void >> miniflow_map_init(struct miniflow *flow, const struct flow *src) >> { >> - const uint64_t *src_u64 = (const uint64_t *) src; >> - int i; >> - >> /* Initialize map, counting the number of nonzero elements. */ >> - flow->tnl_map = 0; >> - for (i = 0; i < FLOW_TNL_U64S; i++) { >> - if (src_u64[i]) { >> - flow->tnl_map |= UINT64_C(1) << i; >> - } >> - } >> - src_u64 += FLOW_TNL_U64S; >> - flow->pkt_map = 0; >> - for (i = 0; i < FLOW_U64S - FLOW_TNL_U64S; i++) { >> - if (src_u64[i]) { >> - flow->pkt_map |= UINT64_C(1) << i; >> + flowmap_init(&flow->map); >> + for (size_t i = 0; i < FLOW_U64S; i++) { >> + if (flow_u64_value(src, i)) { >> + flowmap_set(&flow->map, i, 1); >> } >> } >> } >> @@ -2317,26 +2306,16 @@ miniflow_equal(const struct miniflow *a, const >> struct miniflow *b) >> const uint64_t *ap = miniflow_get_values(a); >> const uint64_t *bp = miniflow_get_values(b); >> >> - if (OVS_LIKELY(miniflow_equal_maps(a, b))) { >> + /* This is mostly called after a matching hash, so it is highly likely >> that >> + * the maps are equal as well. */ >> + if (OVS_LIKELY(flowmap_equal(a->map, b->map))) { >> return !memcmp(ap, bp, miniflow_n_values(a) * sizeof *ap); >> } else { >> - uint64_t map; >> - >> - map = a->tnl_map | b->tnl_map; >> - for (; map; map = zero_rightmost_1bit(map)) { >> - uint64_t bit = rightmost_1bit(map); >> - >> - if ((a->tnl_map & bit ? *ap++ : 0) >> - != (b->tnl_map & bit ? *bp++ : 0)) { >> - return false; >> - } >> - } >> - map = a->pkt_map | b->pkt_map; >> - for (; map; map = zero_rightmost_1bit(map)) { >> - uint64_t bit = rightmost_1bit(map); >> + size_t idx; >> >> - if ((a->pkt_map & bit ? *ap++ : 0) >> - != (b->pkt_map & bit ? *bp++ : 0)) { >> + FLOWMAP_FOR_EACH_INDEX (idx, flowmap_or(a->map, b->map)) { >> + if ((FLOWMAP_IS_SET(a->map, idx) ? *ap++ : 0) >> + != (FLOWMAP_IS_SET(b->map, idx) ? *bp++ : 0)) { >> return false; >> } >> } >> @@ -2354,7 +2333,7 @@ miniflow_equal_in_minimask(const struct miniflow *a, >> const struct miniflow *b, >> const uint64_t *p = miniflow_get_values(&mask->masks); >> size_t idx; >> >> - MAPS_FOR_EACH_INDEX(idx, mask->masks) { >> + FLOWMAP_FOR_EACH_INDEX(idx, mask->masks.map) { >> if ((miniflow_get(a, idx) ^ miniflow_get(b, idx)) & *p++) { >> return false; >> } >> @@ -2369,12 +2348,11 @@ bool >> miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow >> *b, >> const struct minimask *mask) >> { >> - const uint64_t *b_u64 = (const uint64_t *) b; >> const uint64_t *p = miniflow_get_values(&mask->masks); >> size_t idx; >> >> - MAPS_FOR_EACH_INDEX(idx, mask->masks) { >> - if ((miniflow_get(a, idx) ^ b_u64[idx]) & *p++) { >> + FLOWMAP_FOR_EACH_INDEX(idx, mask->masks.map) { >> + if ((miniflow_get(a, idx) ^ flow_u64_value(b, idx)) & *p++) { >> return false; >> } >> } >> @@ -2411,31 +2389,16 @@ minimask_combine(struct minimask *dst_, >> uint64_t *dst_values = storage; >> const struct miniflow *a = &a_->masks; >> const struct miniflow *b = &b_->masks; >> - const uint64_t *ap = miniflow_get_values(a); >> - const uint64_t *bp = miniflow_get_values(b); >> size_t idx; >> >> - dst->tnl_map = 0; >> - MAP_FOR_EACH_INDEX(idx, a->tnl_map & b->tnl_map) { >> - /* Both 'a' and 'b' have non-zero data at 'idx'. */ >> - uint64_t mask = *miniflow_values_get__(ap, a->tnl_map, idx) >> - & *miniflow_values_get__(bp, b->tnl_map, idx); >> + flowmap_init(&dst->map); >> >> - if (mask) { >> - dst->tnl_map |= UINT64_C(1) << idx; >> - *dst_values++ = mask; >> - } >> - } >> - dst->pkt_map = 0; >> - ap += count_1bits(a->tnl_map); /* Skip tnl_map values. */ >> - bp += count_1bits(b->tnl_map); /* Skip tnl_map values. */ >> - MAP_FOR_EACH_INDEX(idx, a->pkt_map & b->pkt_map) { >> + FLOWMAP_FOR_EACH_INDEX(idx, flowmap_and(a->map, b->map)) { >> /* Both 'a' and 'b' have non-zero data at 'idx'. */ >> - uint64_t mask = *miniflow_values_get__(ap, a->pkt_map, idx) >> - & *miniflow_values_get__(bp, b->pkt_map, idx); >> + uint64_t mask = *miniflow_get__(a, idx) & *miniflow_get__(b, idx); >> >> if (mask) { >> - dst->pkt_map |= UINT64_C(1) << idx; >> + flowmap_set(&dst->map, idx, 1); >> *dst_values++ = mask; >> } >> } >> @@ -2454,10 +2417,8 @@ minimask_expand(const struct minimask *mask, struct >> flow_wildcards *wc) >> bool >> minimask_equal(const struct minimask *a, const struct minimask *b) >> { >> - return a->masks.tnl_map == b->masks.tnl_map >> - && a->masks.pkt_map == b->masks.pkt_map && >> - !memcmp(miniflow_get_values(&a->masks), >> miniflow_get_values(&b->masks), >> - MINIFLOW_VALUES_SIZE(miniflow_n_values(&a->masks))); >> + return !memcmp(a, b, sizeof *a >> + + MINIFLOW_VALUES_SIZE(miniflow_n_values(&a->masks))); >> } >> >> /* Returns true if at least one bit matched by 'b' is wildcarded by 'a', >> @@ -2465,28 +2426,16 @@ minimask_equal(const struct minimask *a, const >> struct minimask *b) >> bool >> minimask_has_extra(const struct minimask *a, const struct minimask *b) >> { >> - const uint64_t *ap = miniflow_get_values(&a->masks); >> const uint64_t *bp = miniflow_get_values(&b->masks); >> size_t idx; >> >> - MAP_FOR_EACH_INDEX(idx, b->masks.tnl_map) { >> + FLOWMAP_FOR_EACH_INDEX(idx, b->masks.map) { >> uint64_t b_u64 = *bp++; >> >> /* 'b_u64' is non-zero, check if the data in 'a' is either zero >> * or misses some of the bits in 'b_u64'. */ >> - if (!(a->masks.tnl_map & (UINT64_C(1) << idx)) >> - || ((*miniflow_values_get__(ap, a->masks.tnl_map, idx) & b_u64) >> - != b_u64)) { >> - return true; /* 'a' wildcards some bits 'b' doesn't. */ >> - } >> - } >> - ap += count_1bits(a->masks.tnl_map); /* Skip tnl_map values. */ >> - MAP_FOR_EACH_INDEX(idx, b->masks.pkt_map) { >> - uint64_t b_u64 = *bp++; >> - >> - if (!(a->masks.pkt_map & (UINT64_C(1) << idx)) >> - || ((*miniflow_values_get__(ap, a->masks.pkt_map, idx) & b_u64) >> - != b_u64)) { >> + if (!MINIFLOW_IN_MAP(&a->masks, idx) >> + || ((*miniflow_get__(&a->masks, idx) & b_u64) != b_u64)) { >> return true; /* 'a' wildcards some bits 'b' doesn't. */ >> } >> } >> diff --git a/lib/flow.h b/lib/flow.h >> index 17745ad..ab39060 100644 >> --- a/lib/flow.h >> +++ b/lib/flow.h >> @@ -21,6 +21,7 @@ >> #include <stdbool.h> >> #include <stdint.h> >> #include <string.h> >> +#include "bitmap.h" >> #include "byte-order.h" >> #include "openflow/nicira-ext.h" >> #include "openflow/openflow.h" >> @@ -150,8 +151,6 @@ struct flow { >> }; >> BUILD_ASSERT_DECL(sizeof(struct flow) % sizeof(uint64_t) == 0); >> BUILD_ASSERT_DECL(sizeof(struct flow_tnl) % sizeof(uint64_t) == 0); >> -/* Number of uint64_t units in flow tunnel metadata. */ >> -#define FLOW_TNL_U64S (sizeof(struct flow_tnl) / sizeof(uint64_t)) >> >> #define FLOW_U64S (sizeof(struct flow) / sizeof(uint64_t)) >> >> @@ -192,6 +191,14 @@ 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) >> + >> +/* Number of 64-bit units spanned by a 'FIELD'. */ >> +#define FLOW_U64_SIZE(FIELD) \ >> + DIV_ROUND_UP((FLOW_U64_OFFREM(FIELD) + sizeof(((struct flow >> *)0)->FIELD)), \ >> + sizeof(uint64_t)) >> + >> void flow_extract(struct dp_packet *, struct flow *); >> >> void flow_zero_wildcards(struct flow *, const struct flow_wildcards *); >> @@ -374,13 +381,214 @@ uint32_t flow_hash_in_wildcards(const struct flow *, >> bool flow_equal_except(const struct flow *a, const struct flow *b, >> const struct flow_wildcards *); >> >> -/* Compressed flow. */ >> +/* Bitmap for flow values. For each 1-bit the corresponding flow value is >> + * explicitly specified, other values are zeroes. >> + * >> + * map_t must be wide enough to hold any member of struct flow. */ >> +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))) >> + >> +/* Iterate through the indices of all 1-bits in 'MAP'. */ >> +#define MAP_FOR_EACH_INDEX(IDX, MAP) \ >> + ULLONG_FOR_EACH_1(IDX, MAP) >> + >> +#define FLOWMAP_UNITS DIV_ROUND_UP(FLOW_U64S, MAP_T_BITS) >> + >> +struct flowmap { >> + map_t bits[FLOWMAP_UNITS]; >> +}; >> + >> +#define FLOWMAP_EMPTY_INITIALIZER { { 0 } } >> + >> +static inline void flowmap_init(struct flowmap *); >> +static inline bool flowmap_equal(struct flowmap, struct flowmap); >> +static inline void flowmap_set(struct flowmap *, size_t ofs, size_t n_bits); >> +static inline void flowmap_clear(struct flowmap *, size_t ofs, size_t >> n_bits); >> +static inline struct flowmap flowmap_or(struct flowmap, struct flowmap); >> +static inline struct flowmap flowmap_and(struct flowmap, struct flowmap); >> +static inline bool flowmap_is_empty(struct flowmap); >> +static inline size_t flowmap_n_1bits(struct flowmap); >> + >> +#define FLOWMAP_IS_SET(FM, IDX) \ >> + MAP_IS_SET((FM).bits[(IDX) / MAP_T_BITS], (IDX) % MAP_T_BITS) >> + >> +/* XXX: Assumes 'SIZE' does not span units!. */ >> +#define FLOWMAP_ARE_SET(FM, IDX, SIZE) \ >> + ((FM)->bits[(IDX) / MAP_T_BITS] & \ >> + (((MAP_1 << (SIZE)) - 1) << ((IDX) % MAP_T_BITS))) >> + >> +#define FLOWMAP_HAS_FIELD(FM, FIELD) \ >> + FLOWMAP_ARE_SET(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD)) >> + >> +#define FLOWMAP_SET(FM, FIELD) \ >> + flowmap_set(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD)) >> + >> +/* XXX: Only works for full 64-bit units. */ >> +#define FLOWMAP_CLEAR(FM, FIELD) \ >> + BUILD_ASSERT_DECL(FLOW_U64_OFFREM(FIELD) == 0); \ >> + BUILD_ASSERT_DECL(sizeof(((struct flow *)0)->FIELD) % sizeof(uint64_t) >> == 0); \ >> + flowmap_clear(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD)) >> + >> +/* Iterate through all units in 'FMAP'. */ >> +#define FLOWMAP_FOR_EACH_UNIT(UNIT) \ >> + for ((UNIT) = 0; (UNIT) < FLOWMAP_UNITS; (UNIT)++) >> + >> +/* Iterate through all map units in 'FMAP'. */ >> +#define FLOWMAP_FOR_EACH_MAP(MAP, FLOWMAP) \ >> + for (size_t unit__ = 0; \ >> + unit__ < FLOWMAP_UNITS && ((MAP) = (FLOWMAP).bits[unit__], true); \ >> + unit__++) >> + >> +struct flowmap_aux; >> +static inline bool flowmap_next_index(struct flowmap_aux *, size_t *idx); >> +static inline struct flowmap_aux flowmap_aux_initializer(const struct >> flowmap); >> + >> +/* Iterate through all struct flow u64 indices specified by 'MAP'. This is >> a >> + * slower but easier version of the FLOWMAP_FOR_EACH_MAP() & >> + * MAP_FOR_EACH_INDEX() combination. */ >> +#define FLOWMAP_FOR_EACH_INDEX(IDX, MAP) \ >> + for (struct flowmap_aux aux__ = flowmap_aux_initializer(MAP); \ >> + flowmap_next_index(&aux__, &(IDX));) >> + >> + >> +/* Flowmap inline implementations. */ >> +static inline void >> +flowmap_init(struct flowmap *fm) >> +{ >> + memset(fm, 0, sizeof *fm); >> +} >> + >> +static inline bool >> +flowmap_equal(struct flowmap a, struct flowmap b) >> +{ >> + return !memcmp(&a, &b, sizeof a); >> +} >> >> -/* Check that all tunnel fields fit into a single map. */ >> -BUILD_ASSERT_DECL(FLOW_TNL_U64S <= 64); >> +/* Set the 'n_bits' consecutive bits in 'fm', starting at bit 'ofs'. >> + * 'n_bits' can be at most the number of 64-bit units in the widest member >> + * of struct flow. */ >> +static inline void >> +flowmap_set(struct flowmap *fm, size_t ofs, size_t n_bits) >> +{ >> + map_t n_bits_mask = MAP_MAX >> (MAP_T_BITS - n_bits); >> + size_t unit = ofs / MAP_T_BITS; >> + >> + ofs %= MAP_T_BITS; >> + >> + fm->bits[unit] |= n_bits_mask << ofs; >> + if (unit + 1 < FLOWMAP_UNITS && ofs + n_bits > MAP_T_BITS) { >> + /* 'MAP_T_BITS - ofs' bits were set on 'unit', set the remaining >> + * bits from the next unit. */ >> + fm->bits[unit + 1] |= n_bits_mask >> (MAP_T_BITS - ofs); >> + } >> +} >> + >> +/* Clears the 'n_bits' consecutive bits in 'fm', starting at bit 'ofs'. >> + * 'n_bits' can be at most the number of 64-bit units in the widest member >> + * of struct flow. */ >> +static inline void >> +flowmap_clear(struct flowmap *fm, size_t ofs, size_t n_bits) >> +{ >> + map_t n_bits_mask = MAP_MAX >> (MAP_T_BITS - n_bits); >> + size_t unit = ofs / MAP_T_BITS; >> + >> + ofs %= MAP_T_BITS; >> + >> + fm->bits[unit] &= ~(n_bits_mask << ofs); >> + if (unit + 1 < FLOWMAP_UNITS && ofs + n_bits > MAP_T_BITS) { >> + /* 'MAP_T_BITS - ofs' bits were cleared on 'unit', clear the >> + * remaining bits from the next unit. */ >> + fm->bits[unit + 1] &= ~(n_bits_mask >> (MAP_T_BITS - ofs)); >> + } >> +} >> + >> +/* OR the bits in the flowmaps. */ >> +static inline struct flowmap >> +flowmap_or(struct flowmap a, const struct flowmap b) >> +{ >> + struct flowmap map; >> + size_t unit; >> >> -/* Check that all non-tunnel fields fit into a single map. */ >> -BUILD_ASSERT_DECL(FLOW_U64S - FLOW_TNL_U64S <= 64); >> + FLOWMAP_FOR_EACH_UNIT (unit) { >> + map.bits[unit] = a.bits[unit] | b.bits[unit]; >> + } >> + return map; >> +} >> + >> +/* AND the bits in the flowmaps. */ >> +static inline struct flowmap >> +flowmap_and(struct flowmap a, const struct flowmap b) >> +{ >> + struct flowmap map; >> + size_t unit; >> + >> + FLOWMAP_FOR_EACH_UNIT (unit) { >> + map.bits[unit] = a.bits[unit] & b.bits[unit]; >> + } >> + return map; >> +} >> + >> +static inline bool >> +flowmap_is_empty(const struct flowmap fm) >> +{ >> + map_t map; >> + >> + FLOWMAP_FOR_EACH_MAP (map, fm) { >> + if (map) { >> + return false; >> + } >> + } >> + return true; >> +} >> + >> +static inline size_t >> +flowmap_n_1bits(struct flowmap fm) >> +{ >> + size_t unit, n_1bits = 0; >> + >> + FLOWMAP_FOR_EACH_UNIT (unit) { >> + n_1bits += count_1bits(fm.bits[unit]); >> + } >> + return n_1bits; >> +} >> + >> +struct flowmap_aux { >> + size_t unit; >> + struct flowmap map; >> +}; >> + >> +static inline struct flowmap_aux >> +flowmap_aux_initializer(const struct flowmap fm) >> +{ >> + struct flowmap_aux aux; >> + >> + aux.unit = 0; >> + aux.map = fm; >> + >> + return aux; >> +} >> + >> +static inline bool >> +flowmap_next_index(struct flowmap_aux *aux, size_t *idx) >> +{ >> + map_t *map; >> + >> + while (!*(map = &aux->map.bits[aux->unit])) { >> + if (++aux->unit == FLOWMAP_UNITS) { >> + return false; >> + } >> + } >> + *idx = aux->unit * MAP_T_BITS + raw_ctz(*map); >> + *map = zero_rightmost_1bit(*map); >> + return true; >> +} >> + >> + >> +/* Compressed flow. */ >> >> /* A sparse representation of a "struct flow". >> * >> @@ -389,14 +597,13 @@ BUILD_ASSERT_DECL(FLOW_U64S - FLOW_TNL_U64S <= 64); >> * importantly, minimizes the number of accessed cache lines. Second, it >> saves >> * time when the goal is to iterate over only the nonzero parts of the >> struct. >> * >> - * The map members hold one bit for each uint64_t in a "struct flow". Each >> + * The map member hold one bit for each uint64_t in a "struct flow". Each >> * 0-bit indicates that the corresponding uint64_t is zero, each 1-bit that >> it >> * *may* be nonzero (see below how this applies to minimasks). >> * >> - * The values indicated by 'tnl_map' and 'pkt_map' always follow the >> miniflow >> - * in memory. The user of the miniflow is responsible for always having >> enough >> - * storage after the struct miniflow corresponding to the number of 1-bits >> in >> - * maps. >> + * The values indicated by 'map' always follow the miniflow in memory. The >> + * user of the miniflow is responsible for always having enough storage >> after >> + * the struct miniflow corresponding to the number of 1-bits in maps. >> * >> * 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 >> @@ -407,13 +614,12 @@ BUILD_ASSERT_DECL(FLOW_U64S - FLOW_TNL_U64S <= 64); >> * A miniflow is always dynamically allocated so that the maps are followed >> by >> * at least as many elements as there are 1-bits in maps. */ >> struct miniflow { >> - uint64_t tnl_map; >> - uint64_t pkt_map; >> + struct flowmap map; >> /* Followed by: >> * uint64_t values[n]; >> * where 'n' is miniflow_n_values(miniflow). */ >> }; >> -BUILD_ASSERT_DECL(sizeof(struct miniflow) == 2 * sizeof(uint64_t)); >> +BUILD_ASSERT_DECL(sizeof(struct miniflow) % sizeof(uint64_t) == 0); >> >> #define MINIFLOW_VALUES_SIZE(COUNT) ((COUNT) * sizeof(uint64_t)) >> >> @@ -434,7 +640,7 @@ struct pkt_metadata; >> * were extracted. */ >> void miniflow_extract(struct dp_packet *packet, struct miniflow *dst); >> void miniflow_map_init(struct miniflow *, const struct flow *); >> -void flow_wc_map(const struct flow *, struct miniflow *); >> +void flow_wc_map(const struct flow *, struct flowmap *); >> size_t miniflow_alloc(struct miniflow *dsts[], size_t n, >> const struct miniflow *src); >> void miniflow_init(struct miniflow *, const struct flow *); >> @@ -457,166 +663,127 @@ static inline uint64_t *flow_u64_lvalue(struct flow >> *flow, size_t index) >> static inline size_t >> miniflow_n_values(const struct miniflow *flow) >> { >> - return count_1bits(flow->tnl_map) + count_1bits(flow->pkt_map); >> + return flowmap_n_1bits(flow->map); >> } >> >> struct flow_for_each_in_maps_aux { >> - const uint64_t *values; >> - struct miniflow maps; >> + const struct flow *flow; >> + struct flowmap_aux map_aux; >> }; >> >> -static inline uint64_t >> -flow_values_get_next_in_map(const uint64_t *values, uint64_t *map) >> -{ >> - uint64_t value = values[raw_ctz(*map)]; >> - >> - *map = zero_rightmost_1bit(*map); >> - >> - return value; >> -} >> - >> static inline bool >> flow_values_get_next_in_maps(struct flow_for_each_in_maps_aux *aux, >> uint64_t *value) >> { >> - if (aux->maps.tnl_map) { >> - *value = flow_values_get_next_in_map(aux->values, >> &aux->maps.tnl_map); >> - return true; >> - } >> - if (aux->maps.pkt_map) { >> - *value = flow_values_get_next_in_map(aux->values + FLOW_TNL_U64S, >> - &aux->maps.pkt_map); >> + size_t idx; >> + >> + if (flowmap_next_index(&aux->map_aux, &idx)) { >> + *value = flow_u64_value(aux->flow, idx); >> return true; >> } >> return false; >> } >> >> -/* Iterate through all flow tunnel u64 values specified by 'MAPS'. */ >> +/* Iterate through all flow u64 values specified by 'MAPS'. */ >> #define FLOW_FOR_EACH_IN_MAPS(VALUE, FLOW, MAPS) \ >> for (struct flow_for_each_in_maps_aux aux__ \ >> - = { (const uint64_t *)(FLOW), (MAPS) }; \ >> + = { (FLOW), flowmap_aux_initializer(MAPS) }; \ >> flow_values_get_next_in_maps(&aux__, &(VALUE));) >> >> -/* Iterate through all struct flow u64 indices specified by 'MAP'. */ >> -#define MAP_FOR_EACH_INDEX(U64IDX, MAP) \ >> - for (uint64_t map__ = (MAP); \ >> - map__ && ((U64IDX) = raw_ctz(map__), true); \ >> - map__ = zero_rightmost_1bit(map__)) >> - >> -/* Iterate through all struct flow u64 indices specified by 'MAPS'. */ >> -#define MAPS_FOR_EACH_INDEX(U64IDX, MAPS) \ >> - for (struct miniflow maps__ = (MAPS); \ >> - maps__.tnl_map \ >> - ? ((U64IDX) = raw_ctz(maps__.tnl_map), \ >> - maps__.tnl_map = zero_rightmost_1bit(maps__.tnl_map), \ >> - true) \ >> - : (maps__.pkt_map && \ >> - ((U64IDX) = FLOW_TNL_U64S + raw_ctz(maps__.pkt_map), \ >> - maps__.pkt_map = zero_rightmost_1bit(maps__.pkt_map), \ >> - true));) >> - >> -#define FLOW_U64_SIZE(FIELD) \ >> - DIV_ROUND_UP(sizeof(((struct flow *)0)->FIELD), sizeof(uint64_t)) >> - >> -#define MINIFLOW_TNL_MAP(FIELD) \ >> - (((UINT64_C(1) << FLOW_U64_SIZE(FIELD)) - 1) \ >> - << (offsetof(struct flow, FIELD) / sizeof(uint64_t))) >> -#define MINIFLOW_PKT_MAP(FIELD) \ >> - (((UINT64_C(1) << FLOW_U64_SIZE(FIELD)) - 1) \ >> - << ((offsetof(struct flow, FIELD) / sizeof(uint64_t)) - FLOW_TNL_U64S)) >> - >> struct mf_for_each_in_map_aux { >> + size_t unit; >> + struct flowmap fmap; >> + struct flowmap map; >> const uint64_t *values; >> - uint64_t fmap; >> - uint64_t map; >> }; >> >> static inline bool >> mf_get_next_in_map(struct mf_for_each_in_map_aux *aux, >> uint64_t *value) >> { >> - if (aux->map) { >> - uint64_t rm1bit = rightmost_1bit(aux->map); >> + map_t *map, *fmap; >> + map_t rm1bit; >> >> - aux->map -= rm1bit; >> + while (OVS_UNLIKELY(!*(map = &aux->map.bits[aux->unit]))) { >> + /* Skip remaining data in the previous unit. */ >> + aux->values += count_1bits(aux->fmap.bits[aux->unit]); >> + if (++aux->unit == FLOWMAP_UNITS) { >> + return false; >> + } >> + } >> >> - if (aux->fmap & rm1bit) { >> - uint64_t trash = aux->fmap & (rm1bit - 1); >> + rm1bit = rightmost_1bit(*map); >> + *map -= rm1bit; >> + fmap = &aux->fmap.bits[aux->unit]; >> >> - aux->fmap -= trash; >> - /* count_1bits() is fast for systems where speed matters (e.g., >> - * DPDK), so we don't try avoid using it. >> - * Advance 'aux->values' to point to the value for 'rm1bit'. */ >> - aux->values += count_1bits(trash); >> + if (OVS_LIKELY(*fmap & rm1bit)) { >> + map_t trash = *fmap & (rm1bit - 1); >> >> - *value = *aux->values; >> - } else { >> - *value = 0; >> - } >> - return true; >> + *fmap -= trash; >> + /* count_1bits() is fast for systems where speed matters (e.g., >> + * DPDK), so we don't try avoid using it. >> + * Advance 'aux->values' to point to the value for 'rm1bit'. */ >> + aux->values += count_1bits(trash); >> + >> + *value = *aux->values; >> + } else { >> + *value = 0; >> } >> - return false; >> + return true; >> } >> >> -/* Iterate through miniflow TNL u64 values specified by 'MAPS'. */ >> -#define MINIFLOW_FOR_EACH_IN_TNL_MAP(VALUE, FLOW, MAPS) \ >> - for (struct mf_for_each_in_map_aux aux__ = \ >> - { miniflow_get_values(FLOW), (FLOW)->tnl_map, (MAPS).tnl_map }; \ >> - mf_get_next_in_map(&aux__, &(VALUE));) >> - >> -/* Iterate through miniflow PKT u64 values specified by 'MAPS'. */ >> -#define MINIFLOW_FOR_EACH_IN_PKT_MAP(VALUE, FLOW, MAPS) \ >> +/* Iterate through miniflow u64 values specified by 'FLOWMAP'. */ >> +#define MINIFLOW_FOR_EACH_IN_FLOWMAP(VALUE, FLOW, FLOWMAP) \ >> for (struct mf_for_each_in_map_aux aux__ = \ >> - { miniflow_get_values(FLOW) + count_1bits((FLOW)->tnl_map), \ >> - (FLOW)->pkt_map, (MAPS).pkt_map }; \ >> + { 0, (FLOW)->map, (FLOWMAP), miniflow_get_values(FLOW) }; \ >> mf_get_next_in_map(&aux__, &(VALUE));) >> >> -/* This can be used when it is known that 'u64_idx' is set in 'map'. */ >> +/* This can be used when it is known that 'idx' is set in 'map'. */ >> static inline const uint64_t * >> -miniflow_values_get__(const uint64_t *values, uint64_t map, size_t u64_idx) >> +miniflow_values_get__(const uint64_t *values, map_t map, size_t idx) >> { >> - return values + count_1bits(map & ((UINT64_C(1) << u64_idx) - 1)); >> + return values + count_1bits(map & ((MAP_1 << idx) - 1)); >> } >> >> /* This can be used when it is known that 'u64_idx' is set in >> * the map of 'mf'. */ >> static inline const uint64_t * >> -miniflow_get__(const struct miniflow *mf, size_t u64_idx) >> -{ >> - return OVS_LIKELY(u64_idx >= FLOW_TNL_U64S) >> - ? miniflow_values_get__(miniflow_get_values(mf) >> - + count_1bits(mf->tnl_map), >> - mf->pkt_map, u64_idx - FLOW_TNL_U64S) >> - : miniflow_values_get__(miniflow_get_values(mf), mf->tnl_map, >> u64_idx); >> -} >> - >> -#define MINIFLOW_IN_MAP(MF, U64_IDX) \ >> - (OVS_LIKELY(U64_IDX >= FLOW_TNL_U64S) \ >> - ? (MF)->pkt_map & (UINT64_C(1) << ((U64_IDX) - FLOW_TNL_U64S)) \ >> - : (MF)->tnl_map & (UINT64_C(1) << (U64_IDX))) >> - >> -/* Get the value of 'FIELD' of an up to 8 byte wide integer type 'TYPE' of >> - * a miniflow. */ >> -#define MINIFLOW_GET_TYPE(MF, TYPE, OFS) \ >> - (MINIFLOW_IN_MAP(MF, (OFS) / sizeof(uint64_t)) \ >> - ? ((OVS_FORCE const TYPE *)miniflow_get__(MF, (OFS) / >> sizeof(uint64_t))) \ >> - [(OFS) % sizeof(uint64_t) / sizeof(TYPE)] \ >> +miniflow_get__(const struct miniflow *mf, size_t idx) >> +{ >> + const uint64_t *values = miniflow_get_values(mf); >> + const map_t *map = mf->map.bits; >> + >> + while (idx >= MAP_T_BITS) { >> + idx -= MAP_T_BITS; >> + values += count_1bits(*map++); >> + } >> + return miniflow_values_get__(values, *map, idx); >> +} >> + >> +#define MINIFLOW_IN_MAP(MF, IDX) FLOWMAP_IS_SET((MF)->map, IDX) >> + >> +/* Get the value of the struct flow 'FIELD' as up to 8 byte wide integer >> type >> + * 'TYPE' from miniflow 'MF'. */ >> +#define MINIFLOW_GET_TYPE(MF, TYPE, FIELD) \ >> + (MINIFLOW_IN_MAP(MF, FLOW_U64_OFFSET(FIELD)) \ >> + ? ((OVS_FORCE const TYPE *)miniflow_get__(MF, FLOW_U64_OFFSET(FIELD))) >> \ >> + [FLOW_U64_OFFREM(FIELD) / sizeof(TYPE)] \ >> : 0) >> >> -#define MINIFLOW_GET_U8(FLOW, FIELD) \ >> - MINIFLOW_GET_TYPE(FLOW, uint8_t, offsetof(struct flow, FIELD)) >> -#define MINIFLOW_GET_U16(FLOW, FIELD) \ >> - MINIFLOW_GET_TYPE(FLOW, uint16_t, offsetof(struct flow, FIELD)) >> -#define MINIFLOW_GET_BE16(FLOW, FIELD) \ >> - MINIFLOW_GET_TYPE(FLOW, ovs_be16, offsetof(struct flow, FIELD)) >> -#define MINIFLOW_GET_U32(FLOW, FIELD) \ >> - MINIFLOW_GET_TYPE(FLOW, uint32_t, offsetof(struct flow, FIELD)) >> -#define MINIFLOW_GET_BE32(FLOW, FIELD) \ >> - MINIFLOW_GET_TYPE(FLOW, ovs_be32, offsetof(struct flow, FIELD)) >> -#define MINIFLOW_GET_U64(FLOW, FIELD) \ >> - MINIFLOW_GET_TYPE(FLOW, uint64_t, offsetof(struct flow, FIELD)) >> -#define MINIFLOW_GET_BE64(FLOW, FIELD) \ >> - MINIFLOW_GET_TYPE(FLOW, ovs_be64, offsetof(struct flow, FIELD)) >> +#define MINIFLOW_GET_U8(FLOW, FIELD) \ >> + MINIFLOW_GET_TYPE(FLOW, uint8_t, FIELD) >> +#define MINIFLOW_GET_U16(FLOW, FIELD) \ >> + MINIFLOW_GET_TYPE(FLOW, uint16_t, FIELD) >> +#define MINIFLOW_GET_BE16(FLOW, FIELD) \ >> + MINIFLOW_GET_TYPE(FLOW, ovs_be16, FIELD) >> +#define MINIFLOW_GET_U32(FLOW, FIELD) \ >> + MINIFLOW_GET_TYPE(FLOW, uint32_t, FIELD) >> +#define MINIFLOW_GET_BE32(FLOW, FIELD) \ >> + MINIFLOW_GET_TYPE(FLOW, ovs_be32, FIELD) >> +#define MINIFLOW_GET_U64(FLOW, FIELD) \ >> + MINIFLOW_GET_TYPE(FLOW, uint64_t, FIELD) >> +#define MINIFLOW_GET_BE64(FLOW, FIELD) \ >> + MINIFLOW_GET_TYPE(FLOW, ovs_be64, FIELD) >> >> static inline uint64_t miniflow_get(const struct miniflow *, >> unsigned int u64_ofs); >> @@ -627,8 +794,6 @@ static inline ovs_be32 miniflow_get_be32(const struct >> miniflow *, >> static inline uint16_t miniflow_get_vid(const struct miniflow *); >> static inline uint16_t miniflow_get_tcp_flags(const struct miniflow *); >> static inline ovs_be64 miniflow_get_metadata(const struct miniflow *); >> -static inline bool miniflow_equal_maps(const struct miniflow *a, >> - const struct miniflow *b); >> >> bool miniflow_equal(const struct miniflow *a, const struct miniflow *b); >> bool miniflow_equal_in_minimask(const struct miniflow *a, >> @@ -679,7 +844,7 @@ minimask_is_catchall(const struct minimask *mask) >> /* For every 1-bit in mask's map, the corresponding value is non-zero, >> * so the only way the mask can not fix any bits or fields is for the >> * map the be zero. */ >> - return mask->masks.tnl_map == 0 && mask->masks.pkt_map == 0; >> + return flowmap_is_empty(mask->masks.map); >> } >> >> /* Returns the uint64_t that would be at byte offset '8 * u64_ofs' if 'flow' >> @@ -687,8 +852,7 @@ minimask_is_catchall(const struct minimask *mask) >> static inline uint64_t miniflow_get(const struct miniflow *flow, >> unsigned int u64_ofs) >> { >> - return MINIFLOW_IN_MAP(flow, u64_ofs) >> - ? *miniflow_get__(flow, u64_ofs) : 0; >> + return MINIFLOW_IN_MAP(flow, u64_ofs) ? *miniflow_get__(flow, u64_ofs) >> : 0; >> } >> >> static inline uint32_t miniflow_get_u32(const struct miniflow *flow, >> @@ -754,12 +918,6 @@ miniflow_get_metadata(const struct miniflow *flow) >> return MINIFLOW_GET_BE64(flow, metadata); >> } >> >> -static inline bool >> -miniflow_equal_maps(const struct miniflow *a, const struct miniflow *b) >> -{ >> - return a->tnl_map == b->tnl_map && a->pkt_map == b->pkt_map; >> -} >> - >> /* Returns the mask for the OpenFlow 1.1+ "metadata" field in 'mask'. >> * >> * The return value is all-1-bits if 'mask' matches on the whole value of the >> @@ -781,11 +939,7 @@ flow_union_with_miniflow(struct flow *dst, const struct >> miniflow *src) >> const uint64_t *p = miniflow_get_values(src); >> size_t idx; >> >> - MAP_FOR_EACH_INDEX(idx, src->tnl_map) { >> - dst_u64[idx] |= *p++; >> - } >> - dst_u64 += FLOW_TNL_U64S; >> - MAP_FOR_EACH_INDEX(idx, src->pkt_map) { >> + FLOWMAP_FOR_EACH_INDEX(idx, src->map) { >> dst_u64[idx] |= *p++; >> } >> } >> diff --git a/lib/match.c b/lib/match.c >> index 5175868..0177f82 100644 >> --- a/lib/match.c >> +++ b/lib/match.c >> @@ -1256,13 +1256,12 @@ bool >> minimatch_matches_flow(const struct minimatch *match, >> const struct flow *target) >> { >> - const uint64_t *target_u64 = (const uint64_t *) target; >> const uint64_t *flowp = miniflow_get_values(match->flow); >> const uint64_t *maskp = miniflow_get_values(&match->mask->masks); >> size_t idx; >> >> - MAPS_FOR_EACH_INDEX(idx, *match->flow) { >> - if ((*flowp++ ^ target_u64[idx]) & *maskp++) { >> + FLOWMAP_FOR_EACH_INDEX(idx, match->flow->map) { >> + if ((*flowp++ ^ flow_u64_value(target, idx)) & *maskp++) { >> return false; >> } >> } >> -- >> 2.1.4 >> _______________________________________________ dev mailing list [email protected] http://openvswitch.org/mailman/listinfo/dev
