From d4570fd8ba5f36f21b9b631628e812de0189fa20 Mon Sep 17 00:00:00 2001 From: Jarno Rajahalme Date: Tue, 29 Apr 2014 15:50:38 -0700 Subject: [PATCH] lib/flow: Optimize minimask_has_extra() and minimask_is_catchall() We only need to iterate over the bits masked by the 'b' in minimask_has_extra(), since for zeroes in 'b' there can be no 'extra' wildcards in 'a', as 'b' has already wildcarded all the bits. minimask_is_catchall() can be simplified by the invariant that mask's map never has 1-bits for all-zero values. Signed-off-by: Jarno Rajahalme Acked-by: Ethan Jackson --- lib/flow.c | 31 ++++++------------------------- lib/flow.h | 12 +++++++++++- 2 files changed, 17 insertions(+), 26 deletions(-) diff --git a/lib/flow.c b/lib/flow.c index f7704fb47..211203105 100644 --- a/lib/flow.c +++ b/lib/flow.c @@ -1859,19 +1859,17 @@ minimask_equal(const struct minimask *a, const struct minimask *b) return miniflow_equal(&a->masks, &b->masks); } -/* 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 = b->masks.values; 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; @@ -1880,20 +1878,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; -} diff --git a/lib/flow.h b/lib/flow.h index f0e3a3481..36d453ae4 100644 --- a/lib/flow.h +++ b/lib/flow.h @@ -484,7 +484,17 @@ 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 *); -bool minimask_is_catchall(const struct minimask *); + +/* Returns true if 'mask' matches every packet, false if 'mask' fixes any bits + * or fields. */ +static inline bool +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.map == 0; +} -- 2.43.0