Show a patch.

Update a patch.

Update a patch.

GET /api/patches/1556875/
Content-Type: application/json
Vary: Accept

    "id": 1556875,
    "url": "",
    "web_url": "",
    "project": {
        "id": 47,
        "url": "",
        "name": "Open vSwitch",
        "link_name": "openvswitch",
        "list_id": "",
        "list_email": "",
        "web_url": "",
        "scm_url": "",
        "webscm_url": "",
        "list_archive_url": "",
        "list_archive_url_format": "",
        "commit_url_format": ""
    "msgid": "<>",
    "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": "",
        "name": "Ilya Maximets",
        "email": ""
    "delegate": null,
    "mbox": "",
    "series": [
            "id": 272789,
            "url": "",
            "web_url": "",
            "date": "2021-11-19T02:22:21",
            "name": "[ovs-dev] ovsdb-idl: Re-parse backrefs of inserted rows only once.",
            "version": 1,
            "mbox": ""
    "comments": "",
    "check": "success",
    "checks": "",
    "tags": {},
    "related": [],
    "headers": {
        "Return-Path": "<>",
        "X-Original-To": [
        "Delivered-To": [
        "Authentication-Results": ";\n spf=pass (sender SPF authorized)\n (client-ip=;;\n; receiver=<UNKNOWN>)",
        "Received": [
            "from ( [])\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 (Postfix) with ESMTPS id 4HwL6M4wZQz9sRR\n\tfor <>; Fri, 19 Nov 2021 13:22:35 +1100 (AEDT)",
            "from localhost (localhost [])\n\tby (Postfix) with ESMTP id D55A0409A9;\n\tFri, 19 Nov 2021 02:22:32 +0000 (UTC)",
            "from ([])\n\tby localhost ( []) (amavisd-new, port 10024)\n\twith ESMTP id 7EcGqgpeeV3I; Fri, 19 Nov 2021 02:22:31 +0000 (UTC)",
            "from (\n [IPv6:2605:bc80:3010:104::8cd3:938])\n\tby (Postfix) with ESMTPS id CC31E409A4;\n\tFri, 19 Nov 2021 02:22:30 +0000 (UTC)",
            "from (localhost [])\n\tby (Postfix) with ESMTP id 9B25FC002E;\n\tFri, 19 Nov 2021 02:22:30 +0000 (UTC)",
            "from ( [IPv6:2605:bc80:3010::133])\n by (Postfix) with ESMTP id 3C763C0012\n for <>; Fri, 19 Nov 2021 02:22:29 +0000 (UTC)",
            "from localhost (localhost [])\n by (Postfix) with ESMTP id 17015401D3\n for <>; Fri, 19 Nov 2021 02:22:29 +0000 (UTC)",
            "from ([])\n by localhost ( []) (amavisd-new, port 10024)\n with ESMTP id XeKAlfViwCH8 for <>;\n Fri, 19 Nov 2021 02:22:27 +0000 (UTC)",
            "from (\n [])\n by (Postfix) with ESMTPS id 7422340003\n for <>; Fri, 19 Nov 2021 02:22:27 +0000 (UTC)",
            "(Authenticated sender:\n by (Postfix) with ESMTPSA id 59FFD240004;\n Fri, 19 Nov 2021 02:22:23 +0000 (UTC)"
        "X-Virus-Scanned": [
            "amavisd-new at",
            "amavisd-new at"
        "X-Greylist": "domain auto-whitelisted by SQLgrey-1.8.0",
        "From": "Ilya Maximets <>",
        "To": "",
        "Date": "Fri, 19 Nov 2021 03:22:21 +0100",
        "Message-Id": "<>",
        "X-Mailer": "git-send-email 2.31.1",
        "MIME-Version": "1.0",
        "Cc": "Ilya Maximets <>, Dumitru Ceara <>",
        "Subject": "[ovs-dev] [PATCH] ovsdb-idl: Re-parse backrefs of inserted rows\n\tonly once.",
        "X-BeenThere": "",
        "X-Mailman-Version": "2.1.15",
        "Precedence": "list",
        "List-Id": "<>",
        "List-Unsubscribe": "<>,\n <>",
        "List-Archive": "<>",
        "List-Post": "<>",
        "List-Help": "<>",
        "List-Subscribe": "<>,\n <>",
        "Content-Type": "text/plain; charset=\"us-ascii\"",
        "Content-Transfer-Encoding": "7bit",
        "Errors-To": "",
        "Sender": "\"dev\" <>"
    "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 <>\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": [