@@ -497,6 +497,62 @@ ovsdb_condition_cmp_3way(const struct ovsdb_condition *a,
return 0;
}
+/* Given conditions 'a' and 'b', composes a new condition 'diff' that contains
+ * clauses that are present in one of the conditions, but not in the other.
+ *
+ * If some data doesn't match the resulted 'diff' condition, that means one of:
+ * 1. The data matches both 'a' and 'b'.
+ * 2. The data does not match either 'a' or 'b'.
+ *
+ * However, that is not true if one of the original conditions is a trivial
+ * True or False. In this case the function will currently just return an
+ * empty (True) condition. */
+void
+ovsdb_condition_diff(struct ovsdb_condition *diff,
+ const struct ovsdb_condition *a,
+ const struct ovsdb_condition *b)
+{
+ size_t i, j;
+ int cmp;
+
+ ovsdb_condition_init(diff);
+
+ if (ovsdb_condition_is_trivial(a) || ovsdb_condition_is_trivial(b)) {
+ return;
+ }
+
+ diff->clauses = xcalloc(a->n_clauses + b->n_clauses,
+ sizeof *diff->clauses);
+
+ /* Clauses are sorted. */
+ for (i = j = 0; i < a->n_clauses && j < b->n_clauses;) {
+ cmp = compare_clauses_3way_with_data(&a->clauses[i], &b->clauses[j]);
+ if (cmp < 0) {
+ ovsdb_clause_clone(&diff->clauses[diff->n_clauses++],
+ &a->clauses[i++]);
+ } else if (cmp > 0) {
+ ovsdb_clause_clone(&diff->clauses[diff->n_clauses++],
+ &b->clauses[j++]);
+ } else {
+ i++;
+ j++;
+ }
+ }
+ for (; i < a->n_clauses; i++) {
+ ovsdb_clause_clone(&diff->clauses[diff->n_clauses++],
+ &a->clauses[i]);
+ }
+ for (; j < b->n_clauses; j++) {
+ ovsdb_clause_clone(&diff->clauses[diff->n_clauses++],
+ &b->clauses[j]);
+ }
+
+ diff->optimized = a->optimized && b->optimized;
+ if (diff->optimized) {
+ ovsdb_condition_optimize(diff);
+ }
+}
+
void
ovsdb_condition_clone(struct ovsdb_condition *to,
const struct ovsdb_condition *from)
@@ -58,6 +58,9 @@ bool ovsdb_condition_match_any_clause(const struct ovsdb_datum *,
unsigned int index_map[]);
int ovsdb_condition_cmp_3way(const struct ovsdb_condition *a,
const struct ovsdb_condition *b);
+void ovsdb_condition_diff(struct ovsdb_condition *,
+ const struct ovsdb_condition *,
+ const struct ovsdb_condition *);
void ovsdb_condition_clone(struct ovsdb_condition *to,
const struct ovsdb_condition *from);
bool ovsdb_condition_is_true(const struct ovsdb_condition *cond);
@@ -66,6 +69,12 @@ const struct ovsdb_column **
ovsdb_condition_get_columns(const struct ovsdb_condition *cond,
size_t *n_columns);
+static inline bool
+ovsdb_condition_is_trivial(const struct ovsdb_condition *cond)
+{
+ return ovsdb_condition_is_true(cond) || ovsdb_condition_is_false(cond);
+}
+
static inline bool
ovsdb_condition_empty_or_match_any(const struct ovsdb_datum *row_datum,
const struct ovsdb_condition *cnd,
@@ -55,6 +55,10 @@ struct ovsdb_monitor_table_condition {
struct ovsdb_monitor_table *mt;
struct ovsdb_condition old_condition;
struct ovsdb_condition new_condition;
+
+ /* Condition composed from difference between clauses in old and new.
+ * Note: Empty diff condition doesn't mean that old == new. */
+ struct ovsdb_condition diff_condition;
};
/* Backend monitor.
@@ -713,6 +717,7 @@ ovsdb_monitor_session_condition_destroy(
ovsdb_condition_destroy(&mtc->new_condition);
ovsdb_condition_destroy(&mtc->old_condition);
+ ovsdb_condition_destroy(&mtc->diff_condition);
shash_delete(&condition->tables, node);
free(mtc);
}
@@ -733,6 +738,7 @@ ovsdb_monitor_table_condition_create(
mtc->table = table;
ovsdb_condition_init(&mtc->old_condition);
ovsdb_condition_init(&mtc->new_condition);
+ ovsdb_condition_init(&mtc->diff_condition);
if (json_cnd) {
error = ovsdb_condition_from_json(table->schema,
@@ -746,7 +752,7 @@ ovsdb_monitor_table_condition_create(
}
shash_add(&condition->tables, table->schema->name, mtc);
- /* On session startup old == new condition */
+ /* On session startup old == new condition, diff is empty. */
ovsdb_condition_clone(&mtc->new_condition, &mtc->old_condition);
ovsdb_monitor_session_condition_set_mode(condition);
@@ -758,7 +764,8 @@ ovsdb_monitor_get_table_conditions(
const struct ovsdb_monitor_table *mt,
const struct ovsdb_monitor_session_condition *condition,
struct ovsdb_condition **old_condition,
- struct ovsdb_condition **new_condition)
+ struct ovsdb_condition **new_condition,
+ struct ovsdb_condition **diff_condition)
{
if (!condition) {
return false;
@@ -772,6 +779,7 @@ ovsdb_monitor_get_table_conditions(
}
*old_condition = &mtc->old_condition;
*new_condition = &mtc->new_condition;
+ *diff_condition = &mtc->diff_condition;
return true;
}
@@ -800,6 +808,8 @@ ovsdb_monitor_table_condition_update(
ovsdb_condition_destroy(&mtc->new_condition);
ovsdb_condition_clone(&mtc->new_condition, &cond);
ovsdb_condition_destroy(&cond);
+ ovsdb_condition_diff(&mtc->diff_condition,
+ &mtc->old_condition, &mtc->new_condition);
ovsdb_monitor_condition_add_columns(dbmon,
table,
&mtc->new_condition);
@@ -815,11 +825,14 @@ ovsdb_monitor_table_condition_updated(struct ovsdb_monitor_table *mt,
shash_find_data(&condition->tables, mt->table->schema->name);
if (mtc) {
- /* If conditional monitoring - set old condition to new condition */
+ /* If conditional monitoring - set old condition to new condition
+ * and clear the diff. */
if (ovsdb_condition_cmp_3way(&mtc->old_condition,
&mtc->new_condition)) {
ovsdb_condition_destroy(&mtc->old_condition);
ovsdb_condition_clone(&mtc->old_condition, &mtc->new_condition);
+ ovsdb_condition_destroy(&mtc->diff_condition);
+ ovsdb_condition_init(&mtc->diff_condition);
ovsdb_monitor_session_condition_set_mode(condition);
}
}
@@ -834,29 +847,42 @@ ovsdb_monitor_row_update_type_condition(
const struct ovsdb_datum *old,
const struct ovsdb_datum *new)
{
- struct ovsdb_condition *old_condition, *new_condition;
+ struct ovsdb_condition *old_condition, *new_condition, *diff_condition;
enum ovsdb_monitor_selection type =
ovsdb_monitor_row_update_type(initial, old, new);
if (ovsdb_monitor_get_table_conditions(mt,
condition,
&old_condition,
- &new_condition)) {
- bool old_cond = !old ? false
- : ovsdb_condition_empty_or_match_any(old,
- old_condition,
- row_type == OVSDB_MONITOR_ROW ?
- mt->columns_index_map :
- NULL);
- bool new_cond = !new ? false
- : ovsdb_condition_empty_or_match_any(new,
- new_condition,
- row_type == OVSDB_MONITOR_ROW ?
- mt->columns_index_map :
- NULL);
-
- if (!old_cond && !new_cond) {
+ &new_condition,
+ &diff_condition)) {
+ unsigned int *index_map = row_type == OVSDB_MONITOR_ROW
+ ? mt->columns_index_map : NULL;
+ bool old_cond = false, new_cond = false;
+
+ if (old && old == new
+ && !ovsdb_condition_empty_or_match_any(old, diff_condition,
+ index_map)) {
+ /* Condition changed, but not the data. And the row is not
+ * affected by the condition change. It either mathes or
+ * doesn't match both old and new conditions at the same time.
+ * In any case, this row should not be part of the update. */
type = OJMS_NONE;
+ } else {
+ /* The row changed or the condition change affects this row.
+ * Need to fully check old and new conditions. */
+ if (old) {
+ old_cond = ovsdb_condition_empty_or_match_any(
+ old, old_condition, index_map);
+ }
+ if (new) {
+ new_cond = ovsdb_condition_empty_or_match_any(
+ new, new_condition, index_map);
+ }
+
+ if (!old_cond && !new_cond) {
+ type = OJMS_NONE;
+ }
}
switch (type) {
@@ -1155,15 +1181,16 @@ ovsdb_monitor_compose_cond_change_update(
unsigned long int *changed = xmalloc(bitmap_n_bytes(max_columns));
SHASH_FOR_EACH (node, &dbmon->tables) {
+ struct ovsdb_condition *old_condition, *new_condition, *diff_condition;
struct ovsdb_monitor_table *mt = node->data;
- struct ovsdb_row *row;
struct json *table_json = NULL;
- struct ovsdb_condition *old_condition, *new_condition;
+ struct ovsdb_row *row;
if (!ovsdb_monitor_get_table_conditions(mt,
condition,
&old_condition,
- &new_condition) ||
+ &new_condition,
+ &diff_condition) ||
!ovsdb_condition_cmp_3way(old_condition, new_condition)) {
/* Nothing to update on this table */
continue;
In most cases, after the condition change request, the new condition is the same as old one plus minus a few clauses. Today, ovsdb-server will evaluate every database row against all the old clauses and then against all the new clauses in order to tell if an update should be generated. For example, every time a new port is added, ovn-controller adds two new clauses to conditions for a Port_Binding table. And this condition may grow significantly in size making addition of every new port heavier on the server side. The difference between conditions is not larger and, likely, significantly smaller than old and new conditions combined. And if the row doesn't match clauses that are different between old and new conditions, that row should not be part of the update. It either matches both old and new, or it doesn't match either of them. If the row matches some clauses in the difference, then we need to perform a full match against old and new in order to tell if it should be added/removed/modified. This is necessary because different clauses may select same rows. Let's generate the condition difference and use it to avoid evaluation of all the clauses for rows not affected by the condition change. Testing shows 70% reduction in total CPU time in ovn-heater's 120-node density-light test with conditional monitoring. Average CPU usage during the test phase went down from frequent 100% spikes to just 6-8%. Note: This will not help with new connections, or re-connections, or new monitor requests after database conversion. ovsdb-server will still evaluate every database row against every clause in the condition in these cases. So, it's still important to not have too many clauses in conditions for large tables. Signed-off-by: Ilya Maximets <i.maximets@ovn.org> --- Version 2; - Minor style fixes: empty line, s/xzalloc/xcalloc/. ovsdb/condition.c | 56 +++++++++++++++++++++++++++++++++++++ ovsdb/condition.h | 9 ++++++ ovsdb/monitor.c | 71 ++++++++++++++++++++++++++++++++--------------- 3 files changed, 114 insertions(+), 22 deletions(-)