Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/1529025/?format=api
{ "id": 1529025, "url": "http://patchwork.ozlabs.org/api/patches/1529025/?format=api", "web_url": "http://patchwork.ozlabs.org/project/openvswitch/patch/20210916201522.3693567-1-i.maximets@ovn.org/", "project": { "id": 47, "url": "http://patchwork.ozlabs.org/api/projects/47/?format=api", "name": "Open vSwitch", "link_name": "openvswitch", "list_id": "ovs-dev.openvswitch.org", "list_email": "ovs-dev@openvswitch.org", "web_url": "http://openvswitch.org/", "scm_url": "git@github.com:openvswitch/ovs.git", "webscm_url": "https://github.com/openvswitch/ovs", "list_archive_url": "", "list_archive_url_format": "", "commit_url_format": "" }, "msgid": "<20210916201522.3693567-1-i.maximets@ovn.org>", "list_archive_url": null, "date": "2021-09-16T20:15:22", "name": "[ovs-dev] ovsdb: transaction: Use diffs for strong reference counting.", "commit_ref": null, "pull_url": null, "state": "accepted", "archived": false, "hash": "0eeded0413ce09655c1dc8959068e7e369f63dab", "submitter": { "id": 76798, "url": "http://patchwork.ozlabs.org/api/people/76798/?format=api", "name": "Ilya Maximets", "email": "i.maximets@ovn.org" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/openvswitch/patch/20210916201522.3693567-1-i.maximets@ovn.org/mbox/", "series": [ { "id": 262693, "url": "http://patchwork.ozlabs.org/api/series/262693/?format=api", "web_url": "http://patchwork.ozlabs.org/project/openvswitch/list/?series=262693", "date": "2021-09-16T20:15:22", "name": "[ovs-dev] ovsdb: transaction: Use diffs for strong reference counting.", "version": 1, "mbox": "http://patchwork.ozlabs.org/series/262693/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/1529025/comments/", "check": "warning", "checks": "http://patchwork.ozlabs.org/api/patches/1529025/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<ovs-dev-bounces@openvswitch.org>", "X-Original-To": [ "incoming@patchwork.ozlabs.org", "ovs-dev@openvswitch.org" ], "Delivered-To": [ "patchwork-incoming@ozlabs.org", "ovs-dev@lists.linuxfoundation.org" ], "Authentication-Results": "ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org\n (client-ip=140.211.166.133; helo=smtp2.osuosl.org;\n envelope-from=ovs-dev-bounces@openvswitch.org; receiver=<UNKNOWN>)", "Received": [ "from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest\n SHA256)\n\t(No client certificate requested)\n\tby ozlabs.org (Postfix) with ESMTPS id 4H9Sxz2LzWz9sCD\n\tfor <incoming@patchwork.ozlabs.org>; Fri, 17 Sep 2021 06:15:35 +1000 (AEST)", "from localhost (localhost [127.0.0.1])\n\tby smtp2.osuosl.org (Postfix) with ESMTP id 776D740637;\n\tThu, 16 Sep 2021 20:15:33 +0000 (UTC)", "from smtp2.osuosl.org ([127.0.0.1])\n\tby localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)\n\twith ESMTP id fXjh7jZJ-oFN; Thu, 16 Sep 2021 20:15:32 +0000 (UTC)", "from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56])\n\tby smtp2.osuosl.org (Postfix) with ESMTPS id 20A4640639;\n\tThu, 16 Sep 2021 20:15:31 +0000 (UTC)", "from lf-lists.osuosl.org (localhost [127.0.0.1])\n\tby lists.linuxfoundation.org (Postfix) with ESMTP id D0EF9C000F;\n\tThu, 16 Sep 2021 20:15:30 +0000 (UTC)", "from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])\n by lists.linuxfoundation.org (Postfix) with ESMTP id 7813BC000D\n for <ovs-dev@openvswitch.org>; Thu, 16 Sep 2021 20:15:29 +0000 (UTC)", "from localhost (localhost [127.0.0.1])\n by smtp1.osuosl.org (Postfix) with ESMTP id 5BC1D83F4D\n for <ovs-dev@openvswitch.org>; Thu, 16 Sep 2021 20:15:29 +0000 (UTC)", "from smtp1.osuosl.org ([127.0.0.1])\n by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)\n with ESMTP id ZCPxIXURypwN for <ovs-dev@openvswitch.org>;\n Thu, 16 Sep 2021 20:15:28 +0000 (UTC)", "from relay12.mail.gandi.net (relay12.mail.gandi.net\n [217.70.178.232])\n by smtp1.osuosl.org (Postfix) with ESMTPS id 228F083F51\n for <ovs-dev@openvswitch.org>; Thu, 16 Sep 2021 20:15:27 +0000 (UTC)", "(Authenticated sender: i.maximets@ovn.org)\n by relay12.mail.gandi.net (Postfix) with ESMTPSA id AE512200006;\n Thu, 16 Sep 2021 20:15:24 +0000 (UTC)" ], "X-Virus-Scanned": [ "amavisd-new at osuosl.org", "amavisd-new at osuosl.org" ], "X-Greylist": "domain auto-whitelisted by SQLgrey-1.8.0", "From": "Ilya Maximets <i.maximets@ovn.org>", "To": "ovs-dev@openvswitch.org", "Date": "Thu, 16 Sep 2021 22:15:22 +0200", "Message-Id": "<20210916201522.3693567-1-i.maximets@ovn.org>", "X-Mailer": "git-send-email 2.31.1", "MIME-Version": "1.0", "Cc": "Ilya Maximets <i.maximets@ovn.org>, Dumitru Ceara <dceara@redhat.com>", "Subject": "[ovs-dev] [PATCH] ovsdb: transaction: Use diffs for strong\n\treference counting.", "X-BeenThere": "ovs-dev@openvswitch.org", "X-Mailman-Version": "2.1.15", "Precedence": "list", "List-Id": "<ovs-dev.openvswitch.org>", "List-Unsubscribe": "<https://mail.openvswitch.org/mailman/options/ovs-dev>,\n <mailto:ovs-dev-request@openvswitch.org?subject=unsubscribe>", "List-Archive": "<http://mail.openvswitch.org/pipermail/ovs-dev/>", "List-Post": "<mailto:ovs-dev@openvswitch.org>", "List-Help": "<mailto:ovs-dev-request@openvswitch.org?subject=help>", "List-Subscribe": "<https://mail.openvswitch.org/mailman/listinfo/ovs-dev>,\n <mailto:ovs-dev-request@openvswitch.org?subject=subscribe>", "Content-Type": "text/plain; charset=\"us-ascii\"", "Content-Transfer-Encoding": "7bit", "Errors-To": "ovs-dev-bounces@openvswitch.org", "Sender": "\"dev\" <ovs-dev-bounces@openvswitch.org>" }, "content": "Currently, even if one reference added to the set of strong references\nor removed from it, ovsdb-server will walk through the whole set and\nre-count references to other rows. These referenced rows will also be\nadded to the transaction in order to re-count their references.\n\nFor example, every time Logical Switch Port added to a Logical Switch,\nOVN Northbound database server will walk through all ports of this\nLogical Switch, clone their rows, and re-count references. This is\nnot very efficient. Instead, it can only increase reference counters\nfor added references and reduce for removed ones. In many cases this\nwill be only one row affected in the Logical_Switch_Port table.\n\nIntroducing new function that generates a diff of two datum objects,\nbut stores added and removed atoms separately, so they can be used\nto increase or decrease row reference counters accordingly.\n\nThis change allows to perform several times more transactions that\nadds or removes strong references to/from sets per second, because\novsdb-server no longer clones and re-counts rows that are irrelevant\nto current transaction.\n\nSigned-off-by: Ilya Maximets <i.maximets@ovn.org>\n---\n\nPossible future improvement is to re-use and carry column diff from\nthe file transaction stored in the database file and not re-calculate\non the spot, but this operation is fairly cheap in comparison with\nrow clones.\n\n lib/ovsdb-data.c | 58 +++++++++++++++++++++++++++++++++++++++++++++\n lib/ovsdb-data.h | 6 +++++\n ovsdb/transaction.c | 39 ++++++++++++++++++++++++------\n 3 files changed, 96 insertions(+), 7 deletions(-)", "diff": "diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c\nindex c145f5ad9..17d43d745 100644\n--- a/lib/ovsdb-data.c\n+++ b/lib/ovsdb-data.c\n@@ -2067,6 +2067,64 @@ ovsdb_symbol_table_insert(struct ovsdb_symbol_table *symtab,\n \f\n /* APIs for Generating and apply diffs. */\n \n+/* Find what needs to be added to and removed from 'old' to construct 'new'.\n+ *\n+ * The 'added' and 'removed' datums are always safe; the orders of keys are\n+ * maintained since they are added in order. */\n+void\n+ovsdb_datum_added_removed(struct ovsdb_datum *added,\n+ struct ovsdb_datum *removed,\n+ const struct ovsdb_datum *old,\n+ const struct ovsdb_datum *new,\n+ const struct ovsdb_type *type)\n+{\n+ size_t oi, ni;\n+\n+ ovsdb_datum_init_empty(added);\n+ ovsdb_datum_init_empty(removed);\n+ if (!ovsdb_type_is_composite(type)) {\n+ ovsdb_datum_clone(removed, old, type);\n+ ovsdb_datum_clone(added, new, type);\n+ return;\n+ }\n+\n+ /* Generate the diff in O(n) time. */\n+ for (oi = ni = 0; oi < old->n && ni < new->n; ) {\n+ int c = ovsdb_atom_compare_3way(&old->keys[oi], &new->keys[ni],\n+ type->key.type);\n+ if (c < 0) {\n+ ovsdb_datum_add_unsafe(removed, &old->keys[oi], &old->values[oi],\n+ type, NULL);\n+ oi++;\n+ } else if (c > 0) {\n+ ovsdb_datum_add_unsafe(added, &new->keys[ni], &new->values[ni],\n+ type, NULL);\n+ ni++;\n+ } else {\n+ if (type->value.type != OVSDB_TYPE_VOID &&\n+ ovsdb_atom_compare_3way(&old->values[oi], &new->values[ni],\n+ type->value.type)) {\n+ ovsdb_datum_add_unsafe(removed, &old->keys[oi],\n+ &old->values[oi], type, NULL);\n+ ovsdb_datum_add_unsafe(added, &new->keys[ni], &new->values[ni],\n+ type, NULL);\n+ }\n+ oi++; ni++;\n+ }\n+ }\n+\n+ for (; oi < old->n; oi++) {\n+ ovsdb_datum_add_unsafe(removed, &old->keys[oi], &old->values[oi],\n+ type, NULL);\n+ }\n+\n+ for (; ni < new->n; ni++) {\n+ ovsdb_datum_add_unsafe(added, &new->keys[ni], &new->values[ni],\n+ type, NULL);\n+ }\n+}\n+\n+\n /* Generate a difference ovsdb_dataum between 'old' and 'new'.\n * 'new' can be regenerated by applying the difference to the 'old'.\n *\ndiff --git a/lib/ovsdb-data.h b/lib/ovsdb-data.h\nindex c5a80ee39..aa035ebad 100644\n--- a/lib/ovsdb-data.h\n+++ b/lib/ovsdb-data.h\n@@ -235,6 +235,12 @@ void ovsdb_datum_subtract(struct ovsdb_datum *a,\n const struct ovsdb_type *b_type);\n \n /* Generate and apply diffs */\n+void ovsdb_datum_added_removed(struct ovsdb_datum *added,\n+ struct ovsdb_datum *removed,\n+ const struct ovsdb_datum *old,\n+ const struct ovsdb_datum *new,\n+ const struct ovsdb_type *type);\n+\n void ovsdb_datum_diff(struct ovsdb_datum *diff,\n const struct ovsdb_datum *old_datum,\n const struct ovsdb_datum *new_datum,\ndiff --git a/ovsdb/transaction.c b/ovsdb/transaction.c\nindex 8ffefcf7c..dcccc61c0 100644\n--- a/ovsdb/transaction.c\n+++ b/ovsdb/transaction.c\n@@ -266,9 +266,9 @@ ovsdb_txn_adjust_atom_refs(struct ovsdb_txn *txn, const struct ovsdb_row *r,\n \n static struct ovsdb_error * OVS_WARN_UNUSED_RESULT\n ovsdb_txn_adjust_row_refs(struct ovsdb_txn *txn, const struct ovsdb_row *r,\n- const struct ovsdb_column *column, int delta)\n+ const struct ovsdb_column *column,\n+ const struct ovsdb_datum *field, int delta)\n {\n- const struct ovsdb_datum *field = &r->fields[column->index];\n struct ovsdb_error *error;\n \n error = ovsdb_txn_adjust_atom_refs(txn, r, column, &column->type.key,\n@@ -291,14 +291,39 @@ update_row_ref_count(struct ovsdb_txn *txn, struct ovsdb_txn_row *r)\n struct ovsdb_error *error;\n \n if (bitmap_is_set(r->changed, column->index)) {\n- if (r->old) {\n- error = ovsdb_txn_adjust_row_refs(txn, r->old, column, -1);\n+ if (r->old && !r->new) {\n+ error = ovsdb_txn_adjust_row_refs(\n+ txn, r->old, column,\n+ &r->old->fields[column->index], -1);\n if (error) {\n return OVSDB_WRAP_BUG(\"error decreasing refcount\", error);\n }\n- }\n- if (r->new) {\n- error = ovsdb_txn_adjust_row_refs(txn, r->new, column, 1);\n+ } else if (!r->old && r->new) {\n+ error = ovsdb_txn_adjust_row_refs(\n+ txn, r->new, column,\n+ &r->new->fields[column->index], 1);\n+ if (error) {\n+ return error;\n+ }\n+ } else if (r->old && r->new) {\n+ struct ovsdb_datum added, removed;\n+\n+ ovsdb_datum_added_removed(&added, &removed,\n+ &r->old->fields[column->index],\n+ &r->new->fields[column->index],\n+ &column->type);\n+\n+ error = ovsdb_txn_adjust_row_refs(\n+ txn, r->old, column, &removed, -1);\n+ ovsdb_datum_destroy(&removed, &column->type);\n+ if (error) {\n+ ovsdb_datum_destroy(&added, &column->type);\n+ return OVSDB_WRAP_BUG(\"error decreasing refcount\", error);\n+ }\n+\n+ error = ovsdb_txn_adjust_row_refs(\n+ txn, r->new, column, &added, 1);\n+ ovsdb_datum_destroy(&added, &column->type);\n if (error) {\n return error;\n }\n", "prefixes": [ "ovs-dev" ] }