From patchwork Thu Mar 22 18:42:18 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Han Zhou X-Patchwork-Id: 889549 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="sHmlYg+U"; 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 406bCD3HDjz9s0y for ; Fri, 23 Mar 2018 05:43:04 +1100 (AEDT) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 7F73511EA; Thu, 22 Mar 2018 18:42:40 +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 CF54D1193 for ; Thu, 22 Mar 2018 18:42:36 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-pg0-f68.google.com (mail-pg0-f68.google.com [74.125.83.68]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3E8B35D3 for ; Thu, 22 Mar 2018 18:42:36 +0000 (UTC) Received: by mail-pg0-f68.google.com with SMTP id m15so3620856pgc.1 for ; Thu, 22 Mar 2018 11:42:36 -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=iM512iaH1aon7DG3UfdCiPg2f7UkUDK081qHOH+/GQA=; b=sHmlYg+UsPoJsWl8wnYr0hL4YTGreHz2LuSddATitvuUUcu8Wm85fHOuJ8ijcNIuGf iQMAyjvJ2ArG5p/0JKttNrObOpg8o7ElANzbeLh1XQspxl/AZQUssk4kPJx97+q7WSMo lLLDHXuB4qx7mX8kGxv5WdZcphn82No00FXT7lE3FYI+0wxShJpjrrWiGsn43BC6jcni ktm/zEo16TZPi7reY5xAdhyc+qfmd/tVny6J0UXUfYOz7GYR7Nw1QDZXrFvhxCIFkMJF P2CAqGdbL5+ERQnn++rdamrjlZ1Y11q3tZmJmhfWCsPFy9j/2gQgzhLaq1xcFAdIGmBP nGAA== 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=iM512iaH1aon7DG3UfdCiPg2f7UkUDK081qHOH+/GQA=; b=al+0KPmnKHjAj6uWa30xm4hR4jTZ70nnfQ6lBc74LzV+JYxDc9/G8p6Owh9XTnSnUU xRBrSISou9UkADGn3+umGgBaglI5WiTHjASBld6184sOoftdEUoiIiFh0zd6b1zPikin HsWKSyGCVGIwJKP7AvZxcTNVaHvSCgE1Ctd0Ep9+WYHWwZmZf7XCjCN06apN0GCORjWM 0mtj8WVvjQKRTB3wKU5AotyuFMo5GsvFD2lRKTncZpJfjnv4KcHvlziX8eRXxV2rVqKx HUycfEDoXUHvFndFHwEgPNAUPqeahLE2itvwR9ALCDlf+j9EOtFBo4+6zQ8IdEUeIfNm /l9g== X-Gm-Message-State: AElRT7Gd0/lPTE9FGlmeQdT9knlok3yuVkHFyuCfSpyHVFJYl53wTfU7 EXYTsQ/oyluE+6oN9c8KNzl6gQ== X-Google-Smtp-Source: AG47ELvdk7tTlwL7N9Z2HHxCK7ehLSQEsQtDPeBjbyeJz++SdlvS0yQYoWNpSMZeliCzlshAlVr8bw== X-Received: by 10.99.147.25 with SMTP id b25mr4413167pge.309.1521744155551; Thu, 22 Mar 2018 11:42:35 -0700 (PDT) Received: from localhost.localdomain.localdomain ([216.113.160.71]) by smtp.gmail.com with ESMTPSA id d83sm9959319pfl.176.2018.03.22.11.42.34 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 22 Mar 2018 11:42:35 -0700 (PDT) From: Han Zhou X-Google-Original-From: Han Zhou To: dev@openvswitch.org Date: Thu, 22 Mar 2018 11:42:18 -0700 Message-Id: <1521744147-23451-2-git-send-email-hzhou8@ebay.com> X-Mailer: git-send-email 2.1.0 In-Reply-To: <1521744147-23451-1-git-send-email-hzhou8@ebay.com> References: <1521744147-23451-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 v2 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. --- ovn/lib/automake.mk | 4 +- ovn/lib/inc-proc-eng.c | 97 ++++++++++++++++++++++++++++++++++++++++ ovn/lib/inc-proc-eng.h | 118 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 218 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..c13a065 --- /dev/null +++ b/ovn/lib/inc-proc-eng.c @@ -0,0 +1,97 @@ +/* + * 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); + +bool engine_force_recompute = false; + +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..99c61a1 --- /dev/null +++ b/ovn/lib/inc-proc-eng.h @@ -0,0 +1,118 @@ +/* + * 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 + +// TODO: add documentation of incremental processing engine. + +#define ENGINE_MAX_INPUT 256 + +struct engine_node; + +struct engine_node_input { + struct engine_node *node; + /* change_handler handles one input change against "old_data" of all + * other inputs, returns: + * - true: if change can be handled + * - false: if change cannot be handled (suggesting full recompute) + */ + bool (*change_handler)(struct engine_node *node); +}; + +struct engine_node { + uint64_t run_id; + char* name; + size_t n_inputs; + struct engine_node_input inputs[ENGINE_MAX_INPUT]; + void *data; + bool changed; + void *context; + void (*run)(struct engine_node *node); +}; + +void +engine_run(struct engine_node *node, uint64_t run_id); + +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; +} + +static inline void +engine_add_input(struct engine_node *node, struct engine_node *input, + bool (*change_handler)(struct engine_node *node)) +{ + node->inputs[node->n_inputs].node = input; + node->inputs[node->n_inputs].change_handler = change_handler; + node->n_inputs ++; +} + +extern bool engine_force_recompute; +static inline void +engine_set_force_recompute(bool val) +{ + engine_force_recompute = val; +} + +#define ENGINE_NODE(NAME, NAME_STR) \ + struct engine_node en_##NAME = { \ + .name = NAME_STR, \ + .data = &ed_##NAME, \ + .context = &ctx, \ + .run = NAME##_run, \ + }; + +#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(IDL)) { \ + node->changed = true; \ + return; \ + } \ + node->changed = false; \ +} + +#define ENGINE_FUNC_SB(TBL_NAME) \ + ENGINE_FUNC_OVSDB(sb, TBL_NAME, ctx->ovnsb_idl) + +#define ENGINE_FUNC_OVS(TBL_NAME) \ + ENGINE_FUNC_OVSDB(ovs, TBL_NAME, ctx->ovs_idl) + +#define ENGINE_NODE_SB(TBL_NAME, TBL_NAME_STR) \ + void *ed_sb_##TBL_NAME; \ + ENGINE_NODE(sb_##TBL_NAME, TBL_NAME_STR) + +#define ENGINE_NODE_OVS(TBL_NAME, TBL_NAME_STR) \ + void *ed_ovs_##TBL_NAME; \ + ENGINE_NODE(ovs_##TBL_NAME, TBL_NAME_STR) + +#endif /* ovn/lib/inc-proc-eng.h */