From patchwork Wed Jul 25 00:59:28 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Han Zhou X-Patchwork-Id: 948970 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=openvswitch.org (client-ip=140.211.169.12; helo=mail.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="vNl/aF/8"; dkim-atps=neutral Received: from mail.linuxfoundation.org (mail.linuxfoundation.org [140.211.169.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 41Zxjg0b2dz9s0R for ; Wed, 25 Jul 2018 11:00:38 +1000 (AEST) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 79C22DC8; Wed, 25 Jul 2018 00:59:42 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@mail.linuxfoundation.org Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id C8480D9C for ; Wed, 25 Jul 2018 00:59:39 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-pl0-f65.google.com (mail-pl0-f65.google.com [209.85.160.65]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id AE8B2708 for ; Wed, 25 Jul 2018 00:59:38 +0000 (UTC) Received: by mail-pl0-f65.google.com with SMTP id w3-v6so2502242plq.2 for ; Tue, 24 Jul 2018 17:59:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=Kddl474HsPu5vJeUbJcAM8T1f253V89+5h3R/rtEQyQ=; b=vNl/aF/8yy42kVCmFjwKZDi0bMCZGcXqLvPnSFKIC8zhLV0DHCpjEtqilLrrkSp1hK /FKVYuEG1XSf2D4Nn2NJsSF7zmFuyeDtKuTxIuyyUdxCTGLlqaoQ9pdwBV0ndD3z55O5 JCkH0dyQSb6O+765+ffVK5//GPUcJC5hSwD69/VjnZhl3WrkUxO2eyMJc5krHjXEcN2M 3gqoiludrFACPHVCAlBJ84Tri2UJS5z2+C5GQ5LSyHDjSylRXUQneZt1qzi5YW08+zXU DUYWXpiY/8X8shmfhmUhEVnhyMmViDvVqRBL6yj4gemnxcK59Op8ujlrd5NEiOzEkrJ4 6uoA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=Kddl474HsPu5vJeUbJcAM8T1f253V89+5h3R/rtEQyQ=; b=hSllMREpYA995QKBKmyffZMHYZ+FeVJ1j2CdoJZU7c25/mUjW7tA1gwxhE2yhe7j+D sbhOGAgySVZ0x2t5+blpCYY2nbK4OHdvC1Zp8Cdjzk6Pz+HktU5K3H3lcJPFvn/0ZUKr xBVbVLLq+fbFsyuPvdNr5lFkqIqWYaM5+5WW90Z0XbqlA85c0L0qmCtkA4RlPS9DiYY0 Leztjvj4eXXDG2FEQZDm39cZrTJirSqOGHZROpHxPyRwp2DeUbzOJjfWdbIgV1hPmUSa f9XUDbOcYrp2t5migb9FILEv1dn+VyDLljlEONAEyuJVHuVuZeYOSTkfpJaVRdfu8n2t Istg== X-Gm-Message-State: AOUpUlFVQBtgyVvvUWB9Y9BTrMCqOyeuDerzBKv/E1s90Z8UyncN1GJE 8WCgz3sJtlmVFswUtPKrSu1CVeHM X-Google-Smtp-Source: AAOMgpfiBVB7XYw8JQrALPTRiHUPjC7CSQ/Ynh09xvZ5eIxqpm09plpzDK5QrgG2KeeH6GUU72JMwQ== X-Received: by 2002:a17:902:1566:: with SMTP id b35-v6mr18921545plh.135.1532480377957; Tue, 24 Jul 2018 17:59:37 -0700 (PDT) Received: from localhost.localdomain.localdomain ([216.113.160.71]) by smtp.gmail.com with ESMTPSA id g11-v6sm18798424pgi.90.2018.07.24.17.59.37 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 24 Jul 2018 17:59:37 -0700 (PDT) From: Han Zhou X-Google-Original-From: Han Zhou To: dev@openvswitch.org Date: Tue, 24 Jul 2018 17:59:28 -0700 Message-Id: <1532480380-97578-3-git-send-email-hzhou8@ebay.com> X-Mailer: git-send-email 2.1.0 In-Reply-To: <1532480380-97578-1-git-send-email-hzhou8@ebay.com> References: <1532480380-97578-1-git-send-email-hzhou8@ebay.com> X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: [ovs-dev] [RFC 02/14] ovn-controller: Incremental processing engine X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org This patch implements the engine which will be used in future patches for ovn-controller incremental processing. Signed-off-by: Han Zhou --- ovn/lib/automake.mk | 4 +- ovn/lib/inc-proc-eng.c | 201 +++++++++++++++++++++++++++++++++++++++++ ovn/lib/inc-proc-eng.h | 240 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 444 insertions(+), 1 deletion(-) create mode 100644 ovn/lib/inc-proc-eng.c create mode 100644 ovn/lib/inc-proc-eng.h diff --git a/ovn/lib/automake.mk b/ovn/lib/automake.mk index 6178fc2..c1d37c5 100644 --- a/ovn/lib/automake.mk +++ b/ovn/lib/automake.mk @@ -17,7 +17,9 @@ ovn_lib_libovn_la_SOURCES = \ ovn/lib/ovn-util.c \ ovn/lib/ovn-util.h \ ovn/lib/logical-fields.c \ - ovn/lib/logical-fields.h + ovn/lib/logical-fields.h \ + ovn/lib/inc-proc-eng.c \ + ovn/lib/inc-proc-eng.h nodist_ovn_lib_libovn_la_SOURCES = \ ovn/lib/ovn-nb-idl.c \ ovn/lib/ovn-nb-idl.h \ diff --git a/ovn/lib/inc-proc-eng.c b/ovn/lib/inc-proc-eng.c new file mode 100644 index 0000000..1ddea1a --- /dev/null +++ b/ovn/lib/inc-proc-eng.c @@ -0,0 +1,201 @@ +/* + * Copyright (c) 2018 eBay Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include + +#include +#include +#include +#include +#include + +#include "lib/util.h" +#include "openvswitch/dynamic-string.h" +#include "openvswitch/hmap.h" +#include "openvswitch/vlog.h" +#include "inc-proc-eng.h" + +VLOG_DEFINE_THIS_MODULE(inc_proc_eng); + +static bool engine_force_recompute = false; +static const struct engine_context *engine_context; + +void +engine_set_force_recompute(bool val) +{ + engine_force_recompute = val; +} + +const struct engine_context * +engine_get_context(void) +{ + return engine_context; +} + +void +engine_set_context(const struct engine_context *ctx) +{ + engine_context = ctx; +} + +void +engine_init(struct engine_node *node) +{ + for (size_t i = 0; i < node->n_inputs; i++) { + engine_init(node->inputs[i].node); + } + if (node->init) { + node->init(node); + } +} + +void +engine_cleanup(struct engine_node *node) +{ + for (size_t i = 0; i < node->n_inputs; i++) { + engine_cleanup(node->inputs[i].node); + } + if (node->cleanup) { + node->cleanup(node); + } +} + +struct engine_node * +engine_get_input(const char *input_name, struct engine_node *node) +{ + size_t i; + for (i = 0; i < node->n_inputs; i++) { + if (!strcmp(node->inputs[i].node->name, input_name)) { + return node->inputs[i].node; + } + } + OVS_NOT_REACHED(); + return NULL; +} + +void +engine_add_input(struct engine_node *node, struct engine_node *input, + bool (*change_handler)(struct engine_node *)) +{ + ovs_assert(node->n_inputs < ENGINE_MAX_INPUT); + node->inputs[node->n_inputs].node = input; + node->inputs[node->n_inputs].change_handler = change_handler; + node->n_inputs ++; +} + +struct ovsdb_idl_index * +engine_ovsdb_node_get_index(struct engine_node *node, const char *name) +{ + struct ed_type_ovsdb_table *ed = (struct ed_type_ovsdb_table *)node->data; + for (size_t i = 0; i < ed->n_indexes; i++) { + if (!strcmp(ed->indexes[i].name, name)) { + return ed->indexes[i].index; + } + } + OVS_NOT_REACHED(); + return NULL; +} + +void +engine_ovsdb_node_add_index(struct engine_node *node, const char *name, + struct ovsdb_idl_index *index) +{ + struct ed_type_ovsdb_table *ed = (struct ed_type_ovsdb_table *)node->data; + ovs_assert(ed->n_indexes < ENGINE_MAX_OVSDB_INDEX); + + ed->indexes[ed->n_indexes].name = name; + ed->indexes[ed->n_indexes].index = index; + ed->n_indexes ++; +} + +void +engine_run(struct engine_node *node, uint64_t run_id) +{ + if (node->run_id == run_id) { + return; + } + node->run_id = run_id; + + node->changed = false; + if (!node->n_inputs) { + node->run(node); + VLOG_DBG("node: %s, changed: %d", node->name, node->changed); + return; + } + + for (size_t i = 0; i < node->n_inputs; i++) { + engine_run(node->inputs[i].node, run_id); + } + + bool need_compute = false; + bool need_recompute = false; + + if (engine_force_recompute) { + need_recompute = true; + } else { + for (size_t i = 0; i < node->n_inputs; i++) { + if (node->inputs[i].node->changed) { + need_compute = true; + if (!node->inputs[i].change_handler) { + need_recompute = true; + break; + } + } + } + } + + if (need_recompute) { + VLOG_DBG("node: %s, recompute (%s)", node->name, + engine_force_recompute ? "forced" : "triggered"); + node->run(node); + } else if (need_compute) { + for (size_t i = 0; i < node->n_inputs; i++) { + if (node->inputs[i].node->changed) { + VLOG_DBG("node: %s, handle change for input %s", + node->name, node->inputs[i].node->name); + if (!node->inputs[i].change_handler(node)) { + VLOG_DBG("node: %s, can't handle change for input %s, " + "fall back to recompute", + node->name, node->inputs[i].node->name); + node->run(node); + break; + } + } + } + } + + VLOG_DBG("node: %s, changed: %d", node->name, node->changed); +} + +bool +engine_need_run(struct engine_node *node) +{ + size_t i; + + if (!node->n_inputs) { + node->run(node); + VLOG_DBG("input node: %s, changed: %d", node->name, node->changed); + return node->changed; + } + + for (i = 0; i < node->n_inputs; i++) { + if (engine_need_run(node->inputs[i].node)) { + return true; + } + } + + return false; +} diff --git a/ovn/lib/inc-proc-eng.h b/ovn/lib/inc-proc-eng.h new file mode 100644 index 0000000..40378ef --- /dev/null +++ b/ovn/lib/inc-proc-eng.h @@ -0,0 +1,240 @@ +/* + * Copyright (c) 2018 eBay Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef INC_PROC_ENG_H +#define INC_PROC_ENG_H 1 + +/* The Incremental Processing Engine is a framework for incrementally + * processing changes from different inputs. The main user is ovn-controller. + * To compute desired states (e.g. openflow rules) based on many inputs (e.g. + * south-bound DB tables, local OVSDB interfaces, etc.), it is straightforward + * to recompute everything when there is any change in any inputs, but it + * is inefficient when the size of the input data becomes large. Instead, + * tracking the changes and update the desired states based on what's changed + * is more efficient and scalable. However, it is not straightforward to + * implement the change-based processing when there are a big number of + * inputs. In addition, what makes it more complicated is that intermediate + * results needs to be computed, which needs to be reused in different part + * of the processing and finally generates the final desired states. It is + * proved to be difficult and error-prone to implement this kind of complex + * processing by ad-hoc implementation. + * + * This framework is to provide a generic way to solve the above problem. + * It does not understand the processing logic, but provides a unified way + * to describe the inputs and dependencies clearly, with interfaces for + * users to implement the processing logic for how to handle each input + * changes. + * + * The engine is composed of engine_nodes. Each engine_node is either + * an input, an output or both (intermediate result). Each engine node + * maintains its own data, which is persistent across interactions. Each node + * has zero to ENGINE_MAX_INPUT inputs, which creates a DAG (directed + * acyclic graph). For each input of each engine_node, there is a + * change_handler to process changes of that input, and update the data + * of the engine_node. Then the user can simply call the run() method + * of the engine so that the processing will happen in the order according + * to the dependencies defined and handle the changes incrementally. + * + * While the more fine-grained dependencies and change-handlers are + * implemented, the more efficient the processing will be, it is not + * realistic to implement all change-processing for all inputs (and + * intermediate results). The engine doesn't require change-handler to be + * implemented for every input of every node. Users can choose to implement + * the most important change-handlers (for the changes happens most + * frequently) for overall performance. When there is no change_handler + * defined for a certain input on a certain engine_node, the run() method + * of the engine_node will be called to fall-back to a full recompute + * against all its inputs. + */ + +#define ENGINE_MAX_INPUT 256 +#define ENGINE_MAX_OVSDB_INDEX 256 + +struct engine_context { + struct ovsdb_idl_txn *ovs_idl_txn; + struct ovsdb_idl_txn *ovnsb_idl_txn; +}; + +struct engine_node; + +struct engine_node_input { + /* The input node. */ + struct engine_node *node; + + /* Change handler for changes of the input node. The changes may need to be + * evaluated against all the other inputs. Returns: + * - true: if change can be handled + * - false: if change cannot be handled (indicating full recompute needed) + */ + bool (*change_handler)(struct engine_node *node); +}; + +struct engine_node { + /* A unique id to distinguish each iteration of the engine_run(). */ + uint64_t run_id; + + /* A unique name for each node. */ + char *name; + + /* Number of inputs of this node. */ + size_t n_inputs; + + /* Inputs of this node. */ + struct engine_node_input inputs[ENGINE_MAX_INPUT]; + + /* Data of this node. It is vague and interpreted by the related functions. + * The content of the data should be changed only by the change_handlers + * and run() function of the current node. Users should ensure that the + * data is read-only in change-handlers of the nodes that depends on this + * node. */ + void *data; + + /* Whether the data changed in the last engine run. */ + bool changed; + + /* Method to initialize data. It may be NULL. */ + void (*init)(struct engine_node *); + + /* Method to clean up data. It may be NULL. */ + void (*cleanup)(struct engine_node *); + + /* Fully processes all inputs of this node and regenerates the data + * of this node */ + void (*run)(struct engine_node *); +}; + +/* Initialize the data for the engine nodes recursively. It calls each node's + * init() method if not NULL. It should be called before the main loop. */ +void engine_init(struct engine_node *); + +/* Execute the processing recursively, which should be called in the main + * loop. */ +void engine_run(struct engine_node *, uint64_t run_id); + +/* Clean up the data for the engine nodes recursively. It calls each node's + * cleanup() method if not NULL. It should be called before the program + * terminates. */ +void engine_cleanup(struct engine_node *); + +/* Check if engine needs to run, i.e. any change to be processed. */ +bool +engine_need_run(struct engine_node *); + +/* Get the input node with for */ +struct engine_node * engine_get_input(const char *input_name, + struct engine_node *); + +/* Add an input (dependency) for , with corresponding change_handler, + * which can be NULL. If the change_handler is NULL, the engine will not + * be able to process the change incrementally, and will fall back to call + * the run method to recompute. */ +void engine_add_input(struct engine_node *node, struct engine_node *input, + bool (*change_handler)(struct engine_node *)); + +/* Force the engine to recompute everything if set to true. It is used + * in circumstances when we are not sure there is change or not, or + * when there is change but the engine couldn't be executed in that + * iteration, and the change can't be tracked across iterations */ +void engine_set_force_recompute(bool val); + +const struct engine_context * engine_get_context(void); + +void engine_set_context(const struct engine_context *); + +struct ed_ovsdb_index { + const char *name; + struct ovsdb_idl_index *index; +}; + +struct ed_type_ovsdb_table { + const void *table; + size_t n_indexes; + struct ed_ovsdb_index indexes[ENGINE_MAX_OVSDB_INDEX]; +}; + +#define EN_OVSDB_GET(NODE) \ + (((struct ed_type_ovsdb_table *)NODE->data)->table) + +struct ovsdb_idl_index * engine_ovsdb_node_get_index(struct engine_node *, + const char *name); + +void engine_ovsdb_node_add_index(struct engine_node *, const char *name, + struct ovsdb_idl_index *); + +/* Macro to define an engine node. */ +#define ENGINE_NODE(NAME, NAME_STR) \ + struct engine_node en_##NAME = { \ + .name = NAME_STR, \ + .data = &ed_##NAME, \ + .init = en_##NAME##_init, \ + .run = en_##NAME##_run, \ + .cleanup = en_##NAME##_cleanup, \ + }; + +/* Macro to define member functions of an engine node which represents + * a table of OVSDB */ +#define ENGINE_FUNC_OVSDB(DB_NAME, TBL_NAME) \ +static void \ +en_##DB_NAME##_##TBL_NAME##_run(struct engine_node *node) \ +{ \ + static bool first_run = true; \ + if (first_run) { \ + first_run = false; \ + node->changed = true; \ + return; \ + } \ + const struct DB_NAME##rec_##TBL_NAME##_table* table = \ + EN_OVSDB_GET(node); \ + if (DB_NAME##rec_##TBL_NAME##_table_track_get_first(table)) { \ + node->changed = true; \ + return; \ + } \ + node->changed = false; \ +} \ +static void (*en_##DB_NAME##_##TBL_NAME##_init)(struct engine_node *node) \ + = NULL; \ +static void (*en_##DB_NAME##_##TBL_NAME##_cleanup)(struct engine_node *node) \ + = NULL; + +/* Macro to define member functions of an engine node which represents + * a table of OVN SB DB */ +#define ENGINE_FUNC_SB(TBL_NAME) \ + ENGINE_FUNC_OVSDB(sb, TBL_NAME) + +/* Macro to define member functions of an engine node which represents + * a table of open_vswitch DB */ +#define ENGINE_FUNC_OVS(TBL_NAME) \ + ENGINE_FUNC_OVSDB(ovs, TBL_NAME) + +/* Macro to define an engine node which represents a table of OVSDB */ +#define ENGINE_NODE_OVSDB(DB_NAME, DB_NAME_STR, TBL_NAME, TBL_NAME_STR, IDL) \ + struct ed_type_ovsdb_table ed_##DB_NAME##_##TBL_NAME; \ + memset(&ed_##DB_NAME##_##TBL_NAME, 0, sizeof ed_##DB_NAME##_##TBL_NAME); \ + ovs_assert(IDL); \ + ed_##DB_NAME##_##TBL_NAME.table = \ + DB_NAME##rec_##TBL_NAME##_table_get(IDL); \ + ENGINE_NODE(DB_NAME##_##TBL_NAME, DB_NAME_STR"_"TBL_NAME_STR) + +/* Macro to define an engine node which represents a table of OVN SB DB */ +#define ENGINE_NODE_SB(TBL_NAME, TBL_NAME_STR) \ + ENGINE_NODE_OVSDB(sb, "SB", TBL_NAME, TBL_NAME_STR, ovnsb_idl_loop.idl); + +/* Macro to define an engine node which represents a table of open_vswitch + * DB */ +#define ENGINE_NODE_OVS(TBL_NAME, TBL_NAME_STR) \ + ENGINE_NODE_OVSDB(ovs, "OVS", TBL_NAME, TBL_NAME_STR, ovs_idl_loop.idl); + +#endif /* ovn/lib/inc-proc-eng.h */