From patchwork Mon Dec 18 02:02:44 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 1877177 X-Patchwork-Delegate: i.maximets@samsung.com Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=2605:bc80:3010::137; helo=smtp4.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=patchwork.ozlabs.org) Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Stjly1dBwz23yc for ; Mon, 18 Dec 2023 13:03:26 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 311544167F; Mon, 18 Dec 2023 02:03:24 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 311544167F X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 8fVdqH-QBkj2; Mon, 18 Dec 2023 02:03:23 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by smtp4.osuosl.org (Postfix) with ESMTPS id 346AE40164; Mon, 18 Dec 2023 02:03:22 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 346AE40164 Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id F2F53C0077; Mon, 18 Dec 2023 02:03:21 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 0D262C0037 for ; Mon, 18 Dec 2023 02:03:21 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 4737C4051F for ; Mon, 18 Dec 2023 02:03:10 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 4737C4051F X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 0h6xwmV6vsmD for ; Mon, 18 Dec 2023 02:03:09 +0000 (UTC) Received: from relay6-d.mail.gandi.net (relay6-d.mail.gandi.net [IPv6:2001:4b98:dc4:8::226]) by smtp2.osuosl.org (Postfix) with ESMTPS id D467D404FC for ; Mon, 18 Dec 2023 02:03:08 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org D467D404FC Received: by mail.gandi.net (Postfix) with ESMTPSA id 475B8C0002; Mon, 18 Dec 2023 02:03:06 +0000 (UTC) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Mon, 18 Dec 2023 03:02:44 +0100 Message-ID: <20231218020249.3447973-6-i.maximets@ovn.org> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20231218020249.3447973-1-i.maximets@ovn.org> References: <20231218020249.3447973-1-i.maximets@ovn.org> MIME-Version: 1.0 X-GND-Sasl: i.maximets@ovn.org Cc: Ilya Maximets , Dumitru Ceara Subject: [ovs-dev] [PATCH 5/5] ovsdb: transaction: Calculate added/removed from diff. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" In case the difference between 'old' and 'new' rows is readily available, it can be used to construct added/removed datums instead. Diffs are typically much smaller than the column itself. This change more than doubles the performance of a transaction replay. For example, with this change applied, initial read of OVSDB file containing 136K small transactions for large OVN port groups and address sets on my laptop takes 11 seconds vs 24 seconds without. Signed-off-by: Ilya Maximets --- lib/ovsdb-data.c | 26 ++++++++++++++++++++++++++ lib/ovsdb-data.h | 1 + ovsdb/transaction.c | 15 ++++++++++++--- 3 files changed, 39 insertions(+), 3 deletions(-) diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c index f18f74298..f0d7bee23 100644 --- a/lib/ovsdb-data.c +++ b/lib/ovsdb-data.c @@ -2238,6 +2238,8 @@ 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'. + * If the optional 'diff' is porvided, it can be used to speed up processing, + * in case it is smaller than the original 'old' and 'new'. * * The 'added' and 'removed' datums are always safe; the orders of keys are * maintained since they are added in order. */ @@ -2246,6 +2248,7 @@ 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_datum *diff, const struct ovsdb_type *type) { size_t oi, ni; @@ -2258,6 +2261,29 @@ ovsdb_datum_added_removed(struct ovsdb_datum *added, return; } + /* Use diff, if provided, unless it's comparable in size. */ + if (diff && diff->n * 2 < old->n + new->n) { + unsigned int idx; + + for (size_t di = 0; di < diff->n; di++) { + bool found = ovsdb_datum_find_key(old, &diff->keys[di], + type->key.type, &idx); + + if (!found) { + ovsdb_datum_add_from_index_unsafe(added, diff, di, type); + } else { + if (type->value.type != OVSDB_TYPE_VOID + && !ovsdb_atom_equals(&diff->values[di], + &old->values[idx], + type->value.type)) { + ovsdb_datum_add_from_index_unsafe(added, diff, di, type); + } + ovsdb_datum_add_from_index_unsafe(removed, old, idx, 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], diff --git a/lib/ovsdb-data.h b/lib/ovsdb-data.h index f048a8cb0..c0408ee49 100644 --- a/lib/ovsdb-data.h +++ b/lib/ovsdb-data.h @@ -256,6 +256,7 @@ 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_datum *diff, const struct ovsdb_type *type); void ovsdb_datum_diff(struct ovsdb_datum *diff, diff --git a/ovsdb/transaction.c b/ovsdb/transaction.c index b69d03b5a..e1a87bb74 100644 --- a/ovsdb/transaction.c +++ b/ovsdb/transaction.c @@ -347,12 +347,13 @@ update_row_ref_count(struct ovsdb_txn *txn, struct ovsdb_txn_row *r) return error; } } else if (r->old && r->new) { - struct ovsdb_datum added, removed; + struct ovsdb_datum added, removed, *diff; + diff = (r->diff) ? &r->diff->fields[column->index] : NULL; ovsdb_datum_added_removed(&added, &removed, &r->old->fields[column->index], &r->new->fields[column->index], - &column->type); + diff, &column->type); error = ovsdb_txn_adjust_row_refs( txn, r->old, column, &removed, -1); @@ -760,9 +761,13 @@ assess_weak_refs(struct ovsdb_txn *txn, struct ovsdb_txn_row *txn_row) if (datum->n != orig_n || bitmap_is_set(txn_row->changed, column->index)) { if (txn_row->old) { + struct ovsdb_datum *diff; + + diff = (txn_row->diff && datum->n == orig_n) + ? &txn_row->diff->fields[column->index] : NULL; ovsdb_datum_added_removed(&added, &removed, &txn_row->old->fields[column->index], - datum, &column->type); + datum, diff, &column->type); } else { ovsdb_datum_clone(&added, datum); } @@ -790,6 +795,10 @@ assess_weak_refs(struct ovsdb_txn *txn, struct ovsdb_txn_row *txn_row) if (datum->n != orig_n) { bitmap_set1(txn_row->changed, column->index); + /* Can no longer rely on the previous diff. */ + ovsdb_row_destroy(txn_row->diff); + txn_row->diff = NULL; + if (datum->n < column->type.n_min) { const struct uuid *row_uuid = ovsdb_row_get_uuid(txn_row->new); if (zero && !txn_row->old) {