From patchwork Tue May 15 02:23:20 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Han Zhou X-Patchwork-Id: 913394 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="rg/lO+jA"; 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 40lLx53Lm7z9ryk for ; Tue, 15 May 2018 12:24:25 +1000 (AEST) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 45637133F; Tue, 15 May 2018 02:24:03 +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 E86DD1335 for ; Tue, 15 May 2018 02:24:01 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-pl0-f41.google.com (mail-pl0-f41.google.com [209.85.160.41]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F02BB621 for ; Tue, 15 May 2018 02:24:00 +0000 (UTC) Received: by mail-pl0-f41.google.com with SMTP id t12-v6so8467782plo.7 for ; Mon, 14 May 2018 19:24:00 -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=TQJC7PlwAIyWgRpSWEACldKl75R0vpadDlJVIvdO7u0=; b=rg/lO+jAXIJMv+lRTuccRwSkdf+5Geuqf58iR8fMh0iBlYxVzmaOLpUN7yOo198XOX IdrK86LkWsrxN0wcsqbgOZDyukAv0WW1v4vbD6qzV7KIIuRvTV6X9UquNusAicUSAy9g OOP+4vdt37/FKZjzVcC2pISjDifAfWFjOrXAnWs6sC31dvOegiaMgXY4r7UERMSj/dzc Oo/vTHdjC4HKymyojyrLZK/nuRVmtb9BDkOGRRyMUpGlfCdsWm7osiSD8Ex9/VpdRHSb +qd7+efUpZVL5SbBKBzEoe0VLr1Xmjr5PivIH2uXmbvSGZ1rX3vyFcX48PNEvtGIMBvh foZQ== 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=TQJC7PlwAIyWgRpSWEACldKl75R0vpadDlJVIvdO7u0=; b=R16kzRMiZOcZQbTTWd3gXCrBRpUeNZXyaQXmraC9quoFDO0bqw78rHuGxHXDSYf67r aNi6JV1/hpa3+wMiWnDChIdEhwQPD4vflzd4ILnHvT+L6eefrXdR1YF37VJ+5n537B92 tTHUVoQAB3PzdxokYYFS2oyXQr1WSc1lzjqL5KvB2S2VmF7tWhtG6UjYMdIrcMmRvM9Q kInPX83rnZL3tb556v6CE9owpc47vuNyFIlC5OTO8RO3V7c9yUaNNxylH9v3GT6qsLaa Wv/AZ3bPRIFsdk1OocpzUWbgS61Sw4e9sRgsADRkhwP1j/ODWteC0Nyzbyqpf+RsZcyJ BVdg== X-Gm-Message-State: ALKqPwe8IXjMi2tBSj0ZodRdv8ReYp20Ig2Z3JaSOUzwgA5uwozn83+D IecF24DGrZlDqmBgN9FTsbdESQ== X-Google-Smtp-Source: AB8JxZqCLp2eNR0JWgOpGggWuaZT8JbwPC4zPZKBWgN356u9dc6Qrhy5XFaT1aQfEX6yYF00pHty2g== X-Received: by 2002:a17:902:a5c7:: with SMTP id t7-v6mr12409420plq.360.1526351040192; Mon, 14 May 2018 19:24:00 -0700 (PDT) Received: from localhost.localdomain.localdomain ([216.113.160.70]) by smtp.gmail.com with ESMTPSA id j1-v6sm18255417pfh.95.2018.05.14.19.23.59 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 14 May 2018 19:23:59 -0700 (PDT) From: Han Zhou X-Google-Original-From: Han Zhou To: dev@openvswitch.org Date: Mon, 14 May 2018 19:23:20 -0700 Message-Id: <1526351009-14114-2-git-send-email-hzhou8@ebay.com> X-Mailer: git-send-email 2.1.0 In-Reply-To: <1526351009-14114-1-git-send-email-hzhou8@ebay.com> References: <1526351009-14114-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] [PATCH 01/10] 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 | 125 +++++++++++++++++++++++++++ ovn/lib/inc-proc-eng.h | 224 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 352 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..54c7fd6 --- /dev/null +++ b/ovn/lib/inc-proc-eng.c @@ -0,0 +1,125 @@ +/* + * 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 "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; + +void +engine_set_force_recompute(bool val) +{ + engine_force_recompute = val; +} + +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); + } +} + +void +engine_run(struct engine_node *node, uint64_t run_id) +{ + if (node->run_id == run_id) { + return; + } + node->run_id = run_id; + + if (node->changed) { + node->changed = false; + } + if (!node->n_inputs) { + node->run(node); + VLOG_DBG("node: %s, changed: %d", node->name, node->changed); + return; + } + + size_t i; + + for (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 (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 (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); + +} + diff --git a/ovn/lib/inc-proc-eng.h b/ovn/lib/inc-proc-eng.h new file mode 100644 index 0000000..3e0ec16 --- /dev/null +++ b/ovn/lib/inc-proc-eng.h @@ -0,0 +1,224 @@ +/* + * 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 straighforward + * 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 straighforward 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 interations. 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 + +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 is changed in the last engine run */ + bool changed; + + /* Context data for the engine processing, such as OVSDB IDLs */ + void *context; + + /* Method to initialize data. It may be NULL. */ + void (*init)(struct engine_node *node); + + /* Method to clean up data. It may be NULL. */ + void (*cleanup)(struct engine_node *node); + + /* Fully processing all inputs of this node and regenerate the data + * of this node */ + void (*run)(struct engine_node *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 *node); + +/* Execute the processing recursively, which should be called in the main + * loop. */ +void +engine_run(struct engine_node *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 *node); + +/* Get the input node with for */ +static inline 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; + } + } + return NULL; +} + +/* 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 */ +static inline void +engine_add_input(struct engine_node *node, struct engine_node *input, + bool (*change_handler)(struct engine_node *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 ++; +} + +/* 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); + +/* Macro to define an engine node */ +#define ENGINE_NODE(NAME, NAME_STR, CTX) \ + struct engine_node en_##NAME = { \ + .name = NAME_STR, \ + .data = &ed_##NAME, \ + .context = CTX, \ + .init = NAME##_init, \ + .run = NAME##_run, \ + .cleanup = 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, IDL) \ +static void \ +DB_NAME##_##TBL_NAME##_run(struct engine_node *node) \ +{ \ + static bool first_run = true; \ + if (first_run) { \ + first_run = false; \ + node->changed = true; \ + return; \ + } \ + struct controller_ctx *ctx = (struct controller_ctx *)node->context; \ + if (DB_NAME##rec_##TBL_NAME##_track_get_first(ctx->IDL)) { \ + node->changed = true; \ + return; \ + } \ + node->changed = false; \ +} \ +static void (*DB_NAME##_##TBL_NAME##_init)(struct engine_node *node) \ + = NULL; \ +static void (*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, ovnsb_idl) + +/* 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, ovs_idl) + +/* Macro to define an engine node which represents a table of OVN SB DB */ +#define ENGINE_NODE_SB(TBL_NAME, TBL_NAME_STR, CTX) \ + void *ed_sb_##TBL_NAME; \ + ENGINE_NODE(sb_##TBL_NAME, TBL_NAME_STR, CTX) + +/* Macro to define an engine node which represents a table of open_vswitch + * DB */ +#define ENGINE_NODE_OVS(TBL_NAME, TBL_NAME_STR, CTX) \ + void *ed_ovs_##TBL_NAME; \ + ENGINE_NODE(ovs_##TBL_NAME, TBL_NAME_STR, CTX) + +#endif /* ovn/lib/inc-proc-eng.h */