Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/1556875/
{ "id": 1556875, "url": "http://patchwork.ozlabs.org/api/patches/1556875/", "web_url": "http://patchwork.ozlabs.org/project/openvswitch/patch/20211119022221.2566711-1-i.maximets@ovn.org/", "project": { "id": 47, "url": "http://patchwork.ozlabs.org/api/projects/47/", "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": "<20211119022221.2566711-1-i.maximets@ovn.org>", "list_archive_url": null, "date": "2021-11-19T02:22:21", "name": "[ovs-dev] ovsdb-idl: Re-parse backrefs of inserted rows only once.", "commit_ref": "7b8aeadd60c82f99a9d791a7df7c617254654f9d", "pull_url": null, "state": "accepted", "archived": false, "hash": "f2b8a9e4dffaded9c461402cbacf3e50260a1f19", "submitter": { "id": 76798, "url": "http://patchwork.ozlabs.org/api/people/76798/", "name": "Ilya Maximets", "email": "i.maximets@ovn.org" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/openvswitch/patch/20211119022221.2566711-1-i.maximets@ovn.org/mbox/", "series": [ { "id": 272789, "url": "http://patchwork.ozlabs.org/api/series/272789/", "web_url": "http://patchwork.ozlabs.org/project/openvswitch/list/?series=272789", "date": "2021-11-19T02:22:21", "name": "[ovs-dev] ovsdb-idl: Re-parse backrefs of inserted rows only once.", "version": 1, "mbox": "http://patchwork.ozlabs.org/series/272789/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/1556875/comments/", "check": "success", "checks": "http://patchwork.ozlabs.org/api/patches/1556875/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@bilbo.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.137; helo=smtp4.osuosl.org;\n envelope-from=ovs-dev-bounces@openvswitch.org; receiver=<UNKNOWN>)", "Received": [ "from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])\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 bilbo.ozlabs.org (Postfix) with ESMTPS id 4HwL6M4wZQz9sRR\n\tfor <incoming@patchwork.ozlabs.org>; Fri, 19 Nov 2021 13:22:35 +1100 (AEDT)", "from localhost (localhost [127.0.0.1])\n\tby smtp4.osuosl.org (Postfix) with ESMTP id D55A0409A9;\n\tFri, 19 Nov 2021 02:22:32 +0000 (UTC)", "from smtp4.osuosl.org ([127.0.0.1])\n\tby localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)\n\twith ESMTP id 7EcGqgpeeV3I; Fri, 19 Nov 2021 02:22:31 +0000 (UTC)", "from lists.linuxfoundation.org (lf-lists.osuosl.org\n [IPv6:2605:bc80:3010:104::8cd3:938])\n\tby smtp4.osuosl.org (Postfix) with ESMTPS id CC31E409A4;\n\tFri, 19 Nov 2021 02:22:30 +0000 (UTC)", "from lf-lists.osuosl.org (localhost [127.0.0.1])\n\tby lists.linuxfoundation.org (Postfix) with ESMTP id 9B25FC002E;\n\tFri, 19 Nov 2021 02:22:30 +0000 (UTC)", "from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])\n by lists.linuxfoundation.org (Postfix) with ESMTP id 3C763C0012\n for <ovs-dev@openvswitch.org>; Fri, 19 Nov 2021 02:22:29 +0000 (UTC)", "from localhost (localhost [127.0.0.1])\n by smtp2.osuosl.org (Postfix) with ESMTP id 17015401D3\n for <ovs-dev@openvswitch.org>; Fri, 19 Nov 2021 02:22:29 +0000 (UTC)", "from smtp2.osuosl.org ([127.0.0.1])\n by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)\n with ESMTP id XeKAlfViwCH8 for <ovs-dev@openvswitch.org>;\n Fri, 19 Nov 2021 02:22:27 +0000 (UTC)", "from relay1-d.mail.gandi.net (relay1-d.mail.gandi.net\n [217.70.183.193])\n by smtp2.osuosl.org (Postfix) with ESMTPS id 7422340003\n for <ovs-dev@openvswitch.org>; Fri, 19 Nov 2021 02:22:27 +0000 (UTC)", "(Authenticated sender: i.maximets@ovn.org)\n by relay1-d.mail.gandi.net (Postfix) with ESMTPSA id 59FFD240004;\n Fri, 19 Nov 2021 02:22:23 +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": "Fri, 19 Nov 2021 03:22:21 +0100", "Message-Id": "<20211119022221.2566711-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-idl: Re-parse backrefs of inserted rows\n\tonly once.", "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": "While adding new rows ovsdb-idl re-parses all the other rows that\nreferences this new one. For example, current ovn-kubernetes creates\nload balancers and adds the same load balancer to all logical switches\nand logical routers. So, then a new load balancer is added, rows for\nall logical switches and routers re-parsed.\n\nDuring initial database connection (or re-connection with\nmonitor/monitor_cond or moniotr_cond_since with outdated last\ntransaction id) the client downloads the whole content of a database.\nIn case of OVN, there might be already thousands of load balancers\nconfigured. ovsdb-idl will process rows in that initial monitor reply\none-by-one. Therefore, for each load balancer row, it will re-parse\nall rows for switches and routers.\n\nAssuming that we have 120 Logical Switches and 30K load balancers.\nProcessing of the initial monitor reply will take 120 (switch rows) *\n30K (load balancer references in a switch row) * 30K (load balancer\nrows) = 10^11 operations, which may take hours.\n\nRe-parsing doesn't change any internal structures of the IDL. It\ndestroys and re-creates exactly same arcs between rows. The only\nthing that changes is the application-facing array of pointers.\n\nSince internal structures remains intact, suggested solution is to\npostpone the re-parsing of back references until all the monitor\nupdates processed. This way we can re-parse each row only once.\n\nTested in a sandbox with 120 LSs, 120 LRs and 3K LBs, where each\nload balancer added to each LS and LR, by re-statring ovn-northd and\nmeasuring the time spent in ovsdb_idl_run().\n\nBefore the change:\n\n OVN_Southbound: ovsdb_idl_run took: 924 ms\n OVN_Northbound: ovsdb_idl_run took: 825118 ms --> 13.75 minutes!\n\nAfter:\n\n OVN_Southbound: ovsdb_idl_run took: 692 ms\n OVN_Northbound: ovsdb_idl_run took: 1698 ms\n\nSigned-off-by: Ilya Maximets <i.maximets@ovn.org>\n---\n lib/ovsdb-idl-provider.h | 2 ++\n lib/ovsdb-idl.c | 52 +++++++++++++++++++++++++++++++++++++++-\n 2 files changed, 53 insertions(+), 1 deletion(-)", "diff": "diff --git a/lib/ovsdb-idl-provider.h b/lib/ovsdb-idl-provider.h\nindex 0f122e23c..8797686f9 100644\n--- a/lib/ovsdb-idl-provider.h\n+++ b/lib/ovsdb-idl-provider.h\n@@ -75,6 +75,8 @@ struct ovsdb_idl_row {\n struct ovsdb_idl_table *table; /* Containing table. */\n struct ovsdb_datum *old_datum; /* Committed data (null if orphaned). */\n bool parsed; /* Whether the row is parsed. */\n+ struct ovs_list reparse_node; /* Rows that needs to be re-parsed due to\n+ * insertion of a referenced row. */\n \n /* Transactional data. */\n struct ovsdb_datum *new_datum; /* Modified data (null to delete row). */\ndiff --git a/lib/ovsdb-idl.c b/lib/ovsdb-idl.c\nindex 2801a591c..a6323d2b8 100644\n--- a/lib/ovsdb-idl.c\n+++ b/lib/ovsdb-idl.c\n@@ -96,6 +96,9 @@ struct ovsdb_idl {\n struct ovs_list deleted_untracked_rows; /* Stores rows deleted in the\n * current run, that are not yet\n * added to the track_list. */\n+ struct ovs_list rows_to_reparse; /* Stores rows that might need to be\n+ * re-parsed due to insertion of a\n+ * referenced row. */\n };\n \n static struct ovsdb_cs_ops ovsdb_idl_cs_ops;\n@@ -149,6 +152,7 @@ static bool ovsdb_idl_modify_row(struct ovsdb_idl_row *,\n static void ovsdb_idl_parse_update(struct ovsdb_idl *,\n const struct ovsdb_cs_update_event *);\n static void ovsdb_idl_reparse_deleted(struct ovsdb_idl *);\n+static void ovsdb_idl_reparse_refs_to_inserted(struct ovsdb_idl *);\n \n static void ovsdb_idl_txn_process_reply(struct ovsdb_idl *,\n const struct jsonrpc_msg *);\n@@ -169,6 +173,7 @@ static void ovsdb_idl_row_clear_old(struct ovsdb_idl_row *);\n static void ovsdb_idl_row_clear_new(struct ovsdb_idl_row *);\n static void ovsdb_idl_row_clear_arcs(struct ovsdb_idl_row *, bool destroy_dsts);\n static void ovsdb_idl_row_reparse_backrefs(struct ovsdb_idl_row *);\n+static void ovsdb_idl_row_mark_backrefs_for_reparsing(struct ovsdb_idl_row *);\n static void ovsdb_idl_row_track_change(struct ovsdb_idl_row *,\n enum ovsdb_idl_change);\n static void ovsdb_idl_row_untrack_change(struct ovsdb_idl_row *);\n@@ -261,6 +266,8 @@ ovsdb_idl_create_unconnected(const struct ovsdb_idl_class *class,\n .verify_write_only = false,\n .deleted_untracked_rows\n = OVS_LIST_INITIALIZER(&idl->deleted_untracked_rows),\n+ .rows_to_reparse\n+ = OVS_LIST_INITIALIZER(&idl->rows_to_reparse),\n };\n \n uint8_t default_mode = (monitor_everything_by_default\n@@ -372,6 +379,11 @@ ovsdb_idl_clear(struct ovsdb_idl *db)\n */\n ovsdb_idl_reparse_deleted(db);\n \n+ /* Process backrefs of inserted rows, removing them from the\n+ * 'rows_to_reparse' list.\n+ */\n+ ovsdb_idl_reparse_refs_to_inserted(db);\n+\n /* Cleanup all rows; each row gets added to its own table's\n * 'track_list'.\n */\n@@ -411,6 +423,7 @@ ovsdb_idl_clear(struct ovsdb_idl *db)\n /* Free rows deleted from tables with change tracking enabled. */\n ovsdb_idl_track_clear__(db, true);\n ovs_assert(ovs_list_is_empty(&db->deleted_untracked_rows));\n+ ovs_assert(ovs_list_is_empty(&db->rows_to_reparse));\n db->change_seqno++;\n }\n \n@@ -454,6 +467,7 @@ ovsdb_idl_run(struct ovsdb_idl *idl)\n }\n ovsdb_cs_event_destroy(event);\n }\n+ ovsdb_idl_reparse_refs_to_inserted(idl);\n ovsdb_idl_reparse_deleted(idl);\n ovsdb_idl_row_destroy_postprocess(idl);\n }\n@@ -1484,6 +1498,21 @@ ovsdb_idl_reparse_deleted(struct ovsdb_idl *db)\n }\n }\n \n+/* Reparses rows that refer to rows that were inserted in the\n+ * current IDL run. */\n+static void\n+ovsdb_idl_reparse_refs_to_inserted(struct ovsdb_idl *db)\n+{\n+ struct ovsdb_idl_row *row;\n+\n+ LIST_FOR_EACH_POP (row, reparse_node, &db->rows_to_reparse) {\n+ ovsdb_idl_row_unparse(row);\n+ ovsdb_idl_row_clear_arcs(row, false);\n+ ovsdb_idl_row_parse(row);\n+ ovs_list_init(&row->reparse_node);\n+ }\n+}\n+\n static struct ovsdb_idl_row *\n ovsdb_idl_get_row(struct ovsdb_idl_table *table, const struct uuid *uuid)\n {\n@@ -2153,6 +2182,23 @@ ovsdb_idl_row_reparse_backrefs(struct ovsdb_idl_row *row)\n }\n }\n \n+/* Add all backrefs of a row to the 'rows_to_reparse' list, so they can be\n+ * re-parsed later. */\n+static void\n+ovsdb_idl_row_mark_backrefs_for_reparsing(struct ovsdb_idl_row *row)\n+{\n+ struct ovsdb_idl_arc *arc;\n+\n+ LIST_FOR_EACH (arc, dst_node, &row->dst_arcs) {\n+ struct ovsdb_idl_row *ref = arc->src;\n+\n+ if (ovs_list_is_empty(&ref->reparse_node)) {\n+ ovs_list_push_back(&ref->table->idl->rows_to_reparse,\n+ &ref->reparse_node);\n+ }\n+ }\n+}\n+\n static void\n ovsdb_idl_row_track_change(struct ovsdb_idl_row *row,\n enum ovsdb_idl_change change)\n@@ -2186,6 +2232,7 @@ ovsdb_idl_row_create__(const struct ovsdb_idl_table_class *class)\n class->row_init(row);\n ovs_list_init(&row->src_arcs);\n ovs_list_init(&row->dst_arcs);\n+ ovs_list_init(&row->reparse_node);\n hmap_node_nullify(&row->txn_node);\n ovs_list_init(&row->track_node);\n return row;\n@@ -2305,7 +2352,10 @@ ovsdb_idl_insert_row(struct ovsdb_idl_row *row, const struct shash *data)\n ovsdb_idl_row_change(row, data, false, OVSDB_IDL_CHANGE_INSERT);\n ovsdb_idl_row_parse(row);\n \n- ovsdb_idl_row_reparse_backrefs(row);\n+ /* Backrefs will be re-parsed after all updates processed to avoid\n+ * re-parsing same rows more than once if they are referencing more\n+ * than one inserted row. */\n+ ovsdb_idl_row_mark_backrefs_for_reparsing(row);\n ovsdb_idl_add_to_indexes(row);\n }\n \n", "prefixes": [ "ovs-dev" ] }