get:
Show a patch.

patch:
Update a patch.

put:
Update a patch.

GET /api/patches/1556875/
HTTP 200 OK
Allow: GET, PUT, PATCH, HEAD, OPTIONS
Content-Type: application/json
Vary: Accept

{
    "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"
    ]
}