| Message ID | 20210916201522.3693567-1-i.maximets@ovn.org |
|---|---|
| State | Accepted |
| Headers | show |
| Series | [ovs-dev] ovsdb: transaction: Use diffs for strong reference counting. | expand |
| Context | Check | Description |
|---|---|---|
| ovsrobot/apply-robot | warning | apply and check: warning |
| ovsrobot/github-robot-_Build_and_Test | success | github build: passed |
Bleep bloop. Greetings Ilya Maximets, I am a robot and I have tried out your patch.
Thanks for your contribution.
I encountered some error that I wasn't expecting. See the details below.
checkpatch:
ERROR: Inappropriate bracing around statement
#65 FILE: lib/ovsdb-data.c:2093:
for (oi = ni = 0; oi < old->n && ni < new->n; ) {
Lines checked: 184, Warnings: 0, Errors: 1
Please check this out. If you feel there has been an error, please email aconole@redhat.com
Thanks,
0-day Robot
On 9/16/21 22:38, 0-day Robot wrote: > Bleep bloop. Greetings Ilya Maximets, I am a robot and I have tried out your patch. > Thanks for your contribution. > > I encountered some error that I wasn't expecting. See the details below. > > > checkpatch: > ERROR: Inappropriate bracing around statement > #65 FILE: lib/ovsdb-data.c:2093: > for (oi = ni = 0; oi < old->n && ni < new->n; ) { > > Lines checked: 184, Warnings: 0, Errors: 1 > > > Please check this out. If you feel there has been an error, please email aconole@redhat.com > > Thanks, > 0-day Robot > Oh, sorry about that. Seems like I copy-pasted this issue from the ovsdb_datum_diff(). If new version will not be needed, I can fix that before applying the patch. Best regards, Ilya Maximets.
On 9/16/21 10:15 PM, Ilya Maximets wrote: > Currently, even if one reference added to the set of strong references > or removed from it, ovsdb-server will walk through the whole set and > re-count references to other rows. These referenced rows will also be > added to the transaction in order to re-count their references. > > For example, every time Logical Switch Port added to a Logical Switch, > OVN Northbound database server will walk through all ports of this > Logical Switch, clone their rows, and re-count references. This is > not very efficient. Instead, it can only increase reference counters > for added references and reduce for removed ones. In many cases this > will be only one row affected in the Logical_Switch_Port table. > > Introducing new function that generates a diff of two datum objects, > but stores added and removed atoms separately, so they can be used > to increase or decrease row reference counters accordingly. > > This change allows to perform several times more transactions that > adds or removes strong references to/from sets per second, because > ovsdb-server no longer clones and re-counts rows that are irrelevant > to current transaction. > > Signed-off-by: Ilya Maximets <i.maximets@ovn.org> > --- Hi Ilya, I've been trying this patch out and with a micro benchmark that does: - create X rows in table A - create Y rows in table B (non-root) and reference the rows in table B from exactly one row in table A, uniformly distributed, one new row per transaction. - remove the references to all rows in B from table A, one removal per transaction. I got the following results: X=120, Y=250, w/o patch: - ovsdb-server CPU 10.4%, 27 sec X=120, Y=250, w/ patch (gain ~33%): - ovsdb-server CPU 6.9%, 18 sec X=1, Y=30000, w/o patch: - ovsdb-server CPU goes up to 100% and I stopped it after ~15 min while it was still executing the "create" part of the test. X=1, Y=30000, w/ patch: - ovsdb-server CPU 43.2%, 175 sec I was wondering if it makes sense to factor out the common part of ovsdb_datum_added_removed() and ovsdb_datum_diff(). It seems to me that ovsdb_datum_diff(diff, old, new, type) is almost the same as ovsdb_datum_added_removed(diff, diff, old, new, type), we just need to handle the non-composite types separately and deal with the case when 'added' == 'new' if we detect a value changing for a given key. In any case, the code looks OK to me in the current form too, so: Acked-by: Dumitru Ceara <dceara@redhat.com> Regards, Dumitru
On 9/22/21 1:14 PM, Dumitru Ceara wrote: > On 9/16/21 10:15 PM, Ilya Maximets wrote: >> Currently, even if one reference added to the set of strong references >> or removed from it, ovsdb-server will walk through the whole set and >> re-count references to other rows. These referenced rows will also be >> added to the transaction in order to re-count their references. >> >> For example, every time Logical Switch Port added to a Logical Switch, >> OVN Northbound database server will walk through all ports of this >> Logical Switch, clone their rows, and re-count references. This is >> not very efficient. Instead, it can only increase reference counters >> for added references and reduce for removed ones. In many cases this >> will be only one row affected in the Logical_Switch_Port table. >> >> Introducing new function that generates a diff of two datum objects, >> but stores added and removed atoms separately, so they can be used >> to increase or decrease row reference counters accordingly. >> >> This change allows to perform several times more transactions that >> adds or removes strong references to/from sets per second, because >> ovsdb-server no longer clones and re-counts rows that are irrelevant >> to current transaction. >> >> Signed-off-by: Ilya Maximets <i.maximets@ovn.org> >> --- > > Hi Ilya, > > I've been trying this patch out and with a micro benchmark that does: > > - create X rows in table A > - create Y rows in table B (non-root) and reference the rows in table B Sorry, I meant create Y rows for each row in X here, essentially X * Y rows in table B. > from exactly one row in table A, uniformly distributed, one new row per > transaction. > - remove the references to all rows in B from table A, one removal per > transaction. > > I got the following results: > > X=120, Y=250, w/o patch: > - ovsdb-server CPU 10.4%, 27 sec > > X=120, Y=250, w/ patch (gain ~33%): > - ovsdb-server CPU 6.9%, 18 sec > > X=1, Y=30000, w/o patch: > - ovsdb-server CPU goes up to 100% and I stopped it after ~15 min while > it was still executing the "create" part of the test. > > X=1, Y=30000, w/ patch: > - ovsdb-server CPU 43.2%, 175 sec > > I was wondering if it makes sense to factor out the common part of > ovsdb_datum_added_removed() and ovsdb_datum_diff(). It seems to me that > ovsdb_datum_diff(diff, old, new, type) is almost the same as > ovsdb_datum_added_removed(diff, diff, old, new, type), we just need to > handle the non-composite types separately and deal with the case when > 'added' == 'new' if we detect a value changing for a given key. > > In any case, the code looks OK to me in the current form too, so: > > Acked-by: Dumitru Ceara <dceara@redhat.com> > > Regards, > Dumitru >
On 9/22/21 13:16, Dumitru Ceara wrote: > On 9/22/21 1:14 PM, Dumitru Ceara wrote: >> On 9/16/21 10:15 PM, Ilya Maximets wrote: >>> Currently, even if one reference added to the set of strong references >>> or removed from it, ovsdb-server will walk through the whole set and >>> re-count references to other rows. These referenced rows will also be >>> added to the transaction in order to re-count their references. >>> >>> For example, every time Logical Switch Port added to a Logical Switch, >>> OVN Northbound database server will walk through all ports of this >>> Logical Switch, clone their rows, and re-count references. This is >>> not very efficient. Instead, it can only increase reference counters >>> for added references and reduce for removed ones. In many cases this >>> will be only one row affected in the Logical_Switch_Port table. >>> >>> Introducing new function that generates a diff of two datum objects, >>> but stores added and removed atoms separately, so they can be used >>> to increase or decrease row reference counters accordingly. >>> >>> This change allows to perform several times more transactions that >>> adds or removes strong references to/from sets per second, because >>> ovsdb-server no longer clones and re-counts rows that are irrelevant >>> to current transaction. >>> >>> Signed-off-by: Ilya Maximets <i.maximets@ovn.org> >>> --- >> >> Hi Ilya, >> >> I've been trying this patch out and with a micro benchmark that does: >> >> - create X rows in table A >> - create Y rows in table B (non-root) and reference the rows in table B > > Sorry, I meant create Y rows for each row in X here, essentially X * Y > rows in table B. > >> from exactly one row in table A, uniformly distributed, one new row per >> transaction. >> - remove the references to all rows in B from table A, one removal per >> transaction. >> >> I got the following results: >> >> X=120, Y=250, w/o patch: >> - ovsdb-server CPU 10.4%, 27 sec >> >> X=120, Y=250, w/ patch (gain ~33%): >> - ovsdb-server CPU 6.9%, 18 sec >> >> X=1, Y=30000, w/o patch: >> - ovsdb-server CPU goes up to 100% and I stopped it after ~15 min while >> it was still executing the "create" part of the test. >> >> X=1, Y=30000, w/ patch: >> - ovsdb-server CPU 43.2%, 175 sec >> >> I was wondering if it makes sense to factor out the common part of >> ovsdb_datum_added_removed() and ovsdb_datum_diff(). It seems to me that >> ovsdb_datum_diff(diff, old, new, type) is almost the same as >> ovsdb_datum_added_removed(diff, diff, old, new, type), we just need to >> handle the non-composite types separately and deal with the case when >> 'added' == 'new' if we detect a value changing for a given key. I thought about this and it would be great to reduce some code duplication. But I found dealing with corner cases inside he function a bit awkward. Especially the part where we need to check that 'added' == 'new' and add only one of the values to one of the sets and not touch the other one. So, I kept it as is for now. >> >> In any case, the code looks OK to me in the current form too, so: >> >> Acked-by: Dumitru Ceara <dceara@redhat.com> Applied to master. Thanks! Best regards, Ilya Maximets.
On 9/23/21 1:00 AM, Ilya Maximets wrote: >>> I was wondering if it makes sense to factor out the common part of >>> ovsdb_datum_added_removed() and ovsdb_datum_diff(). It seems to me that >>> ovsdb_datum_diff(diff, old, new, type) is almost the same as >>> ovsdb_datum_added_removed(diff, diff, old, new, type), we just need to >>> handle the non-composite types separately and deal with the case when >>> 'added' == 'new' if we detect a value changing for a given key. > > I thought about this and it would be great to reduce some code duplication. > But I found dealing with corner cases inside he function a bit awkward. > Especially the part where we need to check that 'added' == 'new' and add > only one of the values to one of the sets and not touch the other one. I agree, it's not that pretty. > So, I kept it as is for now. > Sounds good to me, thanks!
diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c index c145f5ad9..17d43d745 100644 --- a/lib/ovsdb-data.c +++ b/lib/ovsdb-data.c @@ -2067,6 +2067,64 @@ ovsdb_symbol_table_insert(struct ovsdb_symbol_table *symtab, /* APIs for Generating and apply diffs. */ +/* Find what needs to be added to and removed from 'old' to construct 'new'. + * + * The 'added' and 'removed' datums are always safe; the orders of keys are + * maintained since they are added in order. */ +void +ovsdb_datum_added_removed(struct ovsdb_datum *added, + struct ovsdb_datum *removed, + const struct ovsdb_datum *old, + const struct ovsdb_datum *new, + const struct ovsdb_type *type) +{ + size_t oi, ni; + + ovsdb_datum_init_empty(added); + ovsdb_datum_init_empty(removed); + if (!ovsdb_type_is_composite(type)) { + ovsdb_datum_clone(removed, old, type); + ovsdb_datum_clone(added, new, type); + return; + } + + /* Generate the diff in O(n) time. */ + for (oi = ni = 0; oi < old->n && ni < new->n; ) { + int c = ovsdb_atom_compare_3way(&old->keys[oi], &new->keys[ni], + type->key.type); + if (c < 0) { + ovsdb_datum_add_unsafe(removed, &old->keys[oi], &old->values[oi], + type, NULL); + oi++; + } else if (c > 0) { + ovsdb_datum_add_unsafe(added, &new->keys[ni], &new->values[ni], + type, NULL); + ni++; + } else { + if (type->value.type != OVSDB_TYPE_VOID && + ovsdb_atom_compare_3way(&old->values[oi], &new->values[ni], + type->value.type)) { + ovsdb_datum_add_unsafe(removed, &old->keys[oi], + &old->values[oi], type, NULL); + ovsdb_datum_add_unsafe(added, &new->keys[ni], &new->values[ni], + type, NULL); + } + oi++; ni++; + } + } + + for (; oi < old->n; oi++) { + ovsdb_datum_add_unsafe(removed, &old->keys[oi], &old->values[oi], + type, NULL); + } + + for (; ni < new->n; ni++) { + ovsdb_datum_add_unsafe(added, &new->keys[ni], &new->values[ni], + type, NULL); + } +} + + /* Generate a difference ovsdb_dataum between 'old' and 'new'. * 'new' can be regenerated by applying the difference to the 'old'. * diff --git a/lib/ovsdb-data.h b/lib/ovsdb-data.h index c5a80ee39..aa035ebad 100644 --- a/lib/ovsdb-data.h +++ b/lib/ovsdb-data.h @@ -235,6 +235,12 @@ void ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *b_type); /* Generate and apply diffs */ +void ovsdb_datum_added_removed(struct ovsdb_datum *added, + struct ovsdb_datum *removed, + const struct ovsdb_datum *old, + const struct ovsdb_datum *new, + const struct ovsdb_type *type); + void ovsdb_datum_diff(struct ovsdb_datum *diff, const struct ovsdb_datum *old_datum, const struct ovsdb_datum *new_datum, diff --git a/ovsdb/transaction.c b/ovsdb/transaction.c index 8ffefcf7c..dcccc61c0 100644 --- a/ovsdb/transaction.c +++ b/ovsdb/transaction.c @@ -266,9 +266,9 @@ ovsdb_txn_adjust_atom_refs(struct ovsdb_txn *txn, const struct ovsdb_row *r, static struct ovsdb_error * OVS_WARN_UNUSED_RESULT ovsdb_txn_adjust_row_refs(struct ovsdb_txn *txn, const struct ovsdb_row *r, - const struct ovsdb_column *column, int delta) + const struct ovsdb_column *column, + const struct ovsdb_datum *field, int delta) { - const struct ovsdb_datum *field = &r->fields[column->index]; struct ovsdb_error *error; error = ovsdb_txn_adjust_atom_refs(txn, r, column, &column->type.key, @@ -291,14 +291,39 @@ update_row_ref_count(struct ovsdb_txn *txn, struct ovsdb_txn_row *r) struct ovsdb_error *error; if (bitmap_is_set(r->changed, column->index)) { - if (r->old) { - error = ovsdb_txn_adjust_row_refs(txn, r->old, column, -1); + if (r->old && !r->new) { + error = ovsdb_txn_adjust_row_refs( + txn, r->old, column, + &r->old->fields[column->index], -1); if (error) { return OVSDB_WRAP_BUG("error decreasing refcount", error); } - } - if (r->new) { - error = ovsdb_txn_adjust_row_refs(txn, r->new, column, 1); + } else if (!r->old && r->new) { + error = ovsdb_txn_adjust_row_refs( + txn, r->new, column, + &r->new->fields[column->index], 1); + if (error) { + return error; + } + } else if (r->old && r->new) { + struct ovsdb_datum added, removed; + + ovsdb_datum_added_removed(&added, &removed, + &r->old->fields[column->index], + &r->new->fields[column->index], + &column->type); + + error = ovsdb_txn_adjust_row_refs( + txn, r->old, column, &removed, -1); + ovsdb_datum_destroy(&removed, &column->type); + if (error) { + ovsdb_datum_destroy(&added, &column->type); + return OVSDB_WRAP_BUG("error decreasing refcount", error); + } + + error = ovsdb_txn_adjust_row_refs( + txn, r->new, column, &added, 1); + ovsdb_datum_destroy(&added, &column->type); if (error) { return error; }
Currently, even if one reference added to the set of strong references or removed from it, ovsdb-server will walk through the whole set and re-count references to other rows. These referenced rows will also be added to the transaction in order to re-count their references. For example, every time Logical Switch Port added to a Logical Switch, OVN Northbound database server will walk through all ports of this Logical Switch, clone their rows, and re-count references. This is not very efficient. Instead, it can only increase reference counters for added references and reduce for removed ones. In many cases this will be only one row affected in the Logical_Switch_Port table. Introducing new function that generates a diff of two datum objects, but stores added and removed atoms separately, so they can be used to increase or decrease row reference counters accordingly. This change allows to perform several times more transactions that adds or removes strong references to/from sets per second, because ovsdb-server no longer clones and re-counts rows that are irrelevant to current transaction. Signed-off-by: Ilya Maximets <i.maximets@ovn.org> --- Possible future improvement is to re-use and carry column diff from the file transaction stored in the database file and not re-calculate on the spot, but this operation is fairly cheap in comparison with row clones. lib/ovsdb-data.c | 58 +++++++++++++++++++++++++++++++++++++++++++++ lib/ovsdb-data.h | 6 +++++ ovsdb/transaction.c | 39 ++++++++++++++++++++++++------ 3 files changed, 96 insertions(+), 7 deletions(-)