ovsdb_datum_apply_diff() is heavily used in ovsdb transactions, but it's linear in terms of number of comparisons. And it also clones all the atoms along the way. In most cases size of a diff is much smaller than the size of the original datum, this allows to perform the same operation in-place with only O(diff->n * log2(old->n)) comparisons and O(old->n + diff->n) memory copies with memcpy. Using this function while applying diffs read from the storage gives a significant performance boost and allows to execute much more transactions per second.
Signed-off-by: Ilya Maximets <[email protected]> --- At the first glance this function seems very similar to 'union' and 'subtract' and even more general version of them, but I'm not sure if we can actually combine them somehow without sacrificing code clarity while trying to handle all the corner cases. lib/ovsdb-data.c | 100 ++++++++++++++++++++++++++++++++++++++++++++ lib/ovsdb-data.h | 6 +++ ovsdb/file.c | 10 ++--- tests/ovsdb-data.at | 12 ++++++ tests/test-ovsdb.c | 17 ++++++++ 5 files changed, 139 insertions(+), 6 deletions(-) diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c index 5297f91ed..90f3b4a53 100644 --- a/lib/ovsdb-data.c +++ b/lib/ovsdb-data.c @@ -2247,6 +2247,106 @@ ovsdb_datum_diff(struct ovsdb_datum *diff, } } +/* Apply 'diff' to 'a'. + * + * Return NULL if the 'a' is successfully updated, otherwise, return + * ovsdb_error. */ +struct ovsdb_error * +ovsdb_datum_apply_diff_in_place(struct ovsdb_datum *a, + const struct ovsdb_datum *diff, + const struct ovsdb_type *type) +{ + struct ovsdb_error *error = NULL; + struct ovsdb_datum result; + size_t i, new_size; + unsigned int *idx, pos; + enum { + DIFF_OP_ADD, + DIFF_OP_REMOVE, + DIFF_OP_UPDATE, + } *operation; + + if (!ovsdb_type_is_composite(type)) { + ovsdb_datum_destroy(a, type); + ovsdb_datum_clone(a, diff, type); + return NULL; + } + + operation = xmalloc(diff->n * sizeof *operation); + idx = xmalloc(diff->n * sizeof *idx); + new_size = a->n; + for (i = 0; i < diff->n; i++) { + if (!ovsdb_datum_find_key(a, &diff->keys[i], type->key.type, &pos)) { + operation[i] = DIFF_OP_ADD; + new_size++; + } else if (type->value.type != OVSDB_TYPE_VOID + && !ovsdb_atom_equals(&diff->values[i], &a->values[pos], + type->value.type)) { + operation[i] = DIFF_OP_UPDATE; + } else { + operation[i] = DIFF_OP_REMOVE; + new_size--; + } + idx[i] = pos; + } + + /* Make sure member size of 'new' conforms to type. */ + if (new_size < type->n_min || new_size > type->n_max) { + error = ovsdb_error(NULL, "Datum crated by diff has size error"); + goto exit; + } + + ovsdb_datum_init_empty(&result); + ovsdb_datum_reallocate(&result, type, new_size); + + unsigned int copied = 0; + for (i = 0; i < diff->n; i++) { + pos = idx[i]; + + if (copied < pos) { + /* Copying all atoms that should go before the current one. */ + ovsdb_datum_push_unsafe(&result, a, copied, pos - copied, type); + copied = pos; + } + + switch (operation[i]) { + case DIFF_OP_UPDATE: + case DIFF_OP_ADD: + /* Inserting new atom from 'diff'. */ + ovsdb_atom_clone(&result.keys[result.n], + &diff->keys[i], type->key.type); + if (type->value.type != OVSDB_TYPE_VOID) { + ovsdb_atom_clone(&result.values[result.n], + &diff->values[i], type->value.type); + } + result.n++; + if (operation[i] != DIFF_OP_UPDATE) { + break; + } + /* fall through */ + + case DIFF_OP_REMOVE: + /* Destroying atom. */ + ovsdb_atom_destroy(&a->keys[pos], type->key.type); + if (type->value.type != OVSDB_TYPE_VOID) { + ovsdb_atom_destroy(&a->values[pos], type->value.type); + } + copied++; /* Skipping removed atom. */ + break; + } + } + /* Copying remaining atoms. */ + ovsdb_datum_push_unsafe(&result, a, copied, a->n - copied, type); + a->n = 0; + + ovsdb_datum_swap(&result, a); + ovsdb_datum_destroy(&result, type); +exit: + free(operation); + free(idx); + return error; +} + /* Apply 'diff' to 'old' to regenerate 'new'. * * Return NULL if the 'new' is successfully generated, otherwise, return diff --git a/lib/ovsdb-data.h b/lib/ovsdb-data.h index 4581e792f..b634e97ff 100644 --- a/lib/ovsdb-data.h +++ b/lib/ovsdb-data.h @@ -252,6 +252,12 @@ struct ovsdb_error *ovsdb_datum_apply_diff(struct ovsdb_datum *new_datum, const struct ovsdb_type *type) OVS_WARN_UNUSED_RESULT; +struct ovsdb_error * ovsdb_datum_apply_diff_in_place( + struct ovsdb_datum *a, + const struct ovsdb_datum *diff, + const struct ovsdb_type *type) +OVS_WARN_UNUSED_RESULT; + /* Raw operations that may not maintain the invariants. */ void ovsdb_datum_remove_unsafe(struct ovsdb_datum *, size_t idx, const struct ovsdb_type *); diff --git a/ovsdb/file.c b/ovsdb/file.c index 59220824f..9f44007d9 100644 --- a/ovsdb/file.c +++ b/ovsdb/file.c @@ -113,19 +113,17 @@ ovsdb_file_update_row_from_json(struct ovsdb_row *row, bool converting, if (row_contains_diff && !ovsdb_datum_is_default(&row->fields[column->index], &column->type)) { - struct ovsdb_datum new_datum; - - error = ovsdb_datum_apply_diff(&new_datum, + error = ovsdb_datum_apply_diff_in_place( &row->fields[column->index], &datum, &column->type); ovsdb_datum_destroy(&datum, &column->type); if (error) { return error; } - ovsdb_datum_swap(&datum, &new_datum); + } else { + ovsdb_datum_swap(&row->fields[column->index], &datum); + ovsdb_datum_destroy(&datum, &column->type); } - ovsdb_datum_swap(&row->fields[column->index], &datum); - ovsdb_datum_destroy(&datum, &column->type); } return NULL; diff --git a/tests/ovsdb-data.at b/tests/ovsdb-data.at index 8cd2a26cb..25c6acdac 100644 --- a/tests/ovsdb-data.at +++ b/tests/ovsdb-data.at @@ -846,18 +846,21 @@ OVSDB_CHECK_POSITIVE([generate and apply diff -- integer], [[diff-data '["integer"]' '[0]' '[2]']], [[diff: 2 apply diff: 2 +apply diff in place: 2 OK]]) OVSDB_CHECK_POSITIVE([generate and apply diff -- boolean], [[diff-data '["boolean"]' '[true]' '[false]']], [[diff: false apply diff: false +apply diff in place: false OK]]) OVSDB_CHECK_POSITIVE([generate and apply diff -- string], [[diff-data '["string"]' '["AAA"]' '["BBB"]']], [[diff: "BBB" apply diff: "BBB" +apply diff in place: "BBB" OK]]) dnl Test set modifications. @@ -870,15 +873,19 @@ OVSDB_CHECK_POSITIVE([generate and apply diff -- set], ]], [[diff: ["set",[0,2]] apply diff: ["set",[1,2]] +apply diff in place: ["set",[1,2]] OK diff: 0 apply diff: 1 +apply diff in place: 1 OK diff: ["set",[0,1]] apply diff: ["set",[0,1]] +apply diff in place: ["set",[0,1]] OK diff: ["set",[0,1]] apply diff: ["set",[]] +apply diff in place: ["set",[]] OK]]) dnl Test set modifications causes data to violate set size constrain. @@ -898,18 +905,23 @@ OVSDB_CHECK_POSITIVE([generate and apply diff -- map], ]], [[diff: ["map",[["2 gills","1 chopin"],["2 pints","1 quart"]]] apply diff: ["map",[["2 pints","1 quart"]]] +apply diff in place: ["map",[["2 pints","1 quart"]]] OK diff: ["map",[]] apply diff: ["map",[["2 gills","1 chopin"]]] +apply diff in place: ["map",[["2 gills","1 chopin"]]] OK diff: ["map",[["2 gills","1 chopin"]]] apply diff: ["map",[]] +apply diff in place: ["map",[]] OK diff: ["map",[["2 pints","1 quart"]]] apply diff: ["map",[["2 pints","1 quart"]]] +apply diff in place: ["map",[["2 pints","1 quart"]]] OK diff: ["map",[["2 gills","1 gallon"]]] apply diff: ["map",[["2 gills","1 gallon"]]] +apply diff in place: ["map",[["2 gills","1 gallon"]]] OK]]) OVSDB_CHECK_NEGATIVE([generate and apply diff with map -- size error], diff --git a/tests/test-ovsdb.c b/tests/test-ovsdb.c index 02485b136..86d75dfd9 100644 --- a/tests/test-ovsdb.c +++ b/tests/test-ovsdb.c @@ -512,6 +512,18 @@ do_diff_data(struct ovs_cmdl_context *ctx) ovs_fatal(0, "failed to apply diff"); } + /* Apply diff to 'old' in place. */ + error = ovsdb_datum_apply_diff_in_place(&old, &diff, &type); + if (error) { + char *string = ovsdb_error_to_string_free(error); + ovs_fatal(0, "%s", string); + } + + /* Test to make sure 'old' equals 'new' now. */ + if (!ovsdb_datum_equals(&new, &old, &type)) { + ovs_fatal(0, "failed to apply diff in place"); + } + /* Print diff */ json = ovsdb_datum_to_json(&diff, &type); printf ("diff: "); @@ -522,6 +534,11 @@ do_diff_data(struct ovs_cmdl_context *ctx) printf ("apply diff: "); print_and_free_json(json); + /* Print updated 'old' */ + json = ovsdb_datum_to_json(&old, &type); + printf ("apply diff in place: "); + print_and_free_json(json); + ovsdb_datum_destroy(&new, &type); ovsdb_datum_destroy(&old, &type); ovsdb_datum_destroy(&diff, &type); -- 2.31.1 _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
