While merging conjunctive flows we're creating an ad-hoc hash map of
all the existing conjunctions and then looking up the new ones in that
hash map to avoid duplicates. The logic is fine here, but the creation
of the hash map is expensive. And the way the expression normalization
works today, we can't actually get more than one new conjunction to
add. This means that we're creating a whole hash map just for one
lookup.
It's good to have the generic handling just in case the expression
normalization logic ever changes, but we certainly shouldn't optimize
for a large number of conjunction in a single expression, while there
can be hundreds of conjunctions in the merged desired flow.
Another problem with conjunctive flows is that they are merged in the
unpredictable order due to incremental processing, and recompute has
its own order as well. This makes recompute overwrite all the
conjunctive OpenFlow rules in OVS, which is also expensive.
Fix both issues by keeping the actions in ascending order of the
conjunction IDs and performing a binary search on the actions directly
for the duplicate detection. A side effect of binary search is that
it provides the place where the value should've been, so we can insert
the new conjunction right there if not found to keep the actions
sorted.
Note: It doesn't make sense and would be a bug in the expression
processing code to have multiple dimensions of the same conjunction
fulfilled by the same match, so we only need to compare the IDs.
Performance-wise the lookup should be comparable to the hash lookup,
but without the need to construct the hash table. The insertion into
the middle of the actions is slightly more expensive if performed
multiple times, but should be comparable to the allocation + append
otherwise.
Keeping the actions sorted means that they should not change on
recompute. There might be a tiny chance in case of a hash collision
while choosing conjunction IDs, but it should be small enough to not
be seen in our tests.
In a setup with 3.5K ACLs referencing the same-ish 450 IP addresses and
a port group with ~20 ports, this change reduces the average full
recompute time from 22 to 18 seconds, which is about 18% speed up.
Fixes: 5ad4e5395b9e ("ofctrl: Prevent conjunction duplication")
Reported-at: https://issues.redhat.com/browse/FDP-3319
Signed-off-by: Ilya Maximets <[email protected]>
---
controller/ofctrl.c | 136 ++++++++++++++++++++++++++------------------
tests/ovn-macros.at | 1 -
2 files changed, 81 insertions(+), 56 deletions(-)
diff --git a/controller/ofctrl.c b/controller/ofctrl.c
index 552a35ccf..f3ca6613d 100644
--- a/controller/ofctrl.c
+++ b/controller/ofctrl.c
@@ -1306,55 +1306,104 @@ ofctrl_add_flow_metered(struct ovn_desired_flow_table
*desired_flows,
meter_id, as_info, true);
}
-struct ofpact_ref {
- struct hmap_node hmap_node;
- struct ofpact *ofpact;
-};
-
-static struct ofpact_ref *
-ofpact_ref_find(const struct hmap *refs, const struct ofpact *ofpact)
+static inline void
+ofpacts_replace(struct ovn_flow *flow, struct ofpbuf *replacement)
{
- uint32_t hash = hash_bytes(ofpact, ofpact->len, 0);
+ /* Make sure there is no extra head- or tailroom.
+ * Should be a no-op in most cases. */
+ ofpbuf_trim(replacement);
- struct ofpact_ref *ref;
- HMAP_FOR_EACH_WITH_HASH (ref, hmap_node, hash, refs) {
- if (ofpacts_equal(ref->ofpact, ref->ofpact->len,
- ofpact, ofpact->len)) {
- return ref;
- }
- }
-
- return NULL;
+ free(flow->ofpacts);
+ flow->ofpacts_len = replacement->size;
+ flow->ofpacts = ofpbuf_steal_data(replacement);
}
-static inline void
-ofpacts_append(struct ovn_flow *flow, const struct ofpbuf *append)
+static int
+compare_conjunctions(const void *a_, const void *b_)
{
- size_t new_len = flow->ofpacts_len + append->size;
+ const struct ofpact_conjunction *a = ofpact_get_CONJUNCTION(a_);
+ const struct ofpact_conjunction *b = ofpact_get_CONJUNCTION(b_);
- flow->ofpacts = xrealloc(flow->ofpacts, new_len);
- memcpy((uint8_t *) flow->ofpacts + flow->ofpacts_len,
- append->data, append->size);
- flow->ofpacts_len = new_len;
+ return a->id == b->id ? 0 : (a->id < b->id ? -1 : 1);
}
-static inline struct ofpbuf *
+/* Finds conjunction 'key' in the 'ofpacts' using binary search. 'ofpacts'
+ * must only contain conjunctions in the ascending order of their IDs.
+ *
+ * Returns 'true' if the 'key' is found, setting 'pos' to the offset in
+ * 'ofpacts' where the 'key' is. Otherwise, returns 'false' and sets the
+ * 'pos' to the offset in the 'ofpacts' where the 'key' should have been. */
+static bool
+ofpacts_find_conjunction(const struct ofpact *ofpacts, size_t ofpacts_len,
+ const struct ofpact_conjunction *key, size_t *pos)
+{
+ const uint8_t *data = (const uint8_t *) ofpacts;
+ size_t high = ofpacts_len / sizeof *key;
+ size_t low = 0;
+ size_t idx;
+ int cmp;
+
+ while (low < high) {
+ idx = (low + high) / 2;
+ cmp = compare_conjunctions(key, data + idx * sizeof *key);
+
+ if (cmp < 0) {
+ high = idx;
+ } else if (cmp > 0) {
+ low = idx + 1;
+ } else {
+ if (pos) {
+ *pos = idx * sizeof *key;
+ }
+ return true;
+ }
+ }
+ if (pos) {
+ *pos = low * sizeof *key;
+ }
+ return false;
+}
+
+static struct ofpbuf *
create_conjunction_actions(const struct vector *conjunctions,
- const struct hmap *existing)
+ const struct ovn_flow *existing)
{
size_t len = vector_len(conjunctions);
- struct ofpbuf *ofpbuf =
- ofpbuf_new(sizeof(struct ofpact_conjunction) * len);
+ struct ofpact_conjunction *conj;
+ size_t conj_size = sizeof *conj;
+ struct ofpbuf *ofpbuf;
+ size_t pos;
+
+ if (existing) {
+ ofpbuf = ofpbuf_new(existing->ofpacts_len + conj_size * len);
+ ofpbuf_put(ofpbuf, existing->ofpacts, existing->ofpacts_len);
+ } else {
+ ofpbuf = ofpbuf_new(conj_size * len);
+ }
const struct cls_conjunction *cls;
VECTOR_FOR_EACH_PTR (conjunctions, cls) {
- struct ofpact_conjunction *conj = ofpact_put_CONJUNCTION(ofpbuf);
+ conj = ofpact_put_CONJUNCTION(ofpbuf);
conj->id = cls->id;
conj->clause = cls->clause;
conj->n_clauses = cls->n_clauses;
- if (existing && ofpact_ref_find(existing, &conj->ofpact)) {
+ if (!existing) {
+ continue;
+ }
+
+ if (ofpacts_find_conjunction(ofpbuf->data, ofpbuf->size - conj_size,
+ conj, &pos)) {
+ /* It's a duplicate, drop it. */
+ ofpbuf->size -= sizeof *conj;
+ } else if (pos == ofpbuf->size - conj_size) {
+ /* Not found, but needed to insert at the end anyway. */
+ } else {
+ /* Not found and need to insert in the middle. */
+ struct ofpact_conjunction tmp = *conj;
+
ofpbuf->size -= sizeof *conj;
+ ofpbuf_insert(ofpbuf, pos, &tmp, sizeof tmp);
}
}
@@ -1384,35 +1433,12 @@ ofctrl_add_or_append_conj_flow(struct
ovn_desired_flow_table *desired_flows,
match, NULL, 0, meter_id);
existing = desired_flow_lookup_conjunctive(desired_flows, &search_flow);
if (existing) {
- struct hmap existing_conj = HMAP_INITIALIZER(&existing_conj);
- /* We can calculate the length directly because the flow actions
- * consist only of conjunctions. Make a rough assert to ensure
- * that is that case in the future. */
- size_t conj_size = sizeof(struct ofpact_conjunction);
- ovs_assert(!(existing->flow.ofpacts_len % conj_size));
- struct ofpact_ref *refs =
- xmalloc(sizeof *refs * existing->flow.ofpacts_len / conj_size);
-
- size_t index = 0;
- struct ofpact *ofpact;
- OFPACT_FOR_EACH (ofpact, existing->flow.ofpacts,
- existing->flow.ofpacts_len) {
- ovs_assert(ofpact->type == OFPACT_CONJUNCTION);
- struct ofpact_ref *ref = &refs[index++];
- ref->ofpact = ofpact;
- uint32_t hash = hash_bytes(ofpact, ofpact->len, 0);
- hmap_insert(&existing_conj, &ref->hmap_node, hash);
- }
+ actions = create_conjunction_actions(conjunctions, &existing->flow);
- actions = create_conjunction_actions(conjunctions, &existing_conj);
mem_stats.desired_flow_usage -= desired_flow_size(existing);
- ofpacts_append(&existing->flow, actions);
+ ofpacts_replace(&existing->flow, actions);
mem_stats.desired_flow_usage += desired_flow_size(existing);
-
- free(refs);
- hmap_destroy(&existing_conj);
-
f = existing;
/* Since the flow now shared by more than one SB lflows, don't track
diff --git a/tests/ovn-macros.at b/tests/ovn-macros.at
index aeb4149d5..39f03ba62 100644
--- a/tests/ovn-macros.at
+++ b/tests/ovn-macros.at
@@ -240,7 +240,6 @@ m4_define([DUMP_FLOWS], [
sed 's/, hard_age=[[^,]]*//g' |
sed 's/n_bytes=[[^,]]*/n_bytes=xx/g' |
sed 's/n_packets=[[^,]]*/n_packets=xx/g' |
- sed 's/conjunction([[^,]]*/conjunction(xx/g' |
sort > $output_file
])
--
2.53.0
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
