Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/1525719/?format=api
{ "id": 1525719, "url": "http://patchwork.ozlabs.org/api/patches/1525719/?format=api", "web_url": "http://patchwork.ozlabs.org/project/openvswitch/patch/bea14ca839b11729e634fddf14aa345cd57158fd.1631094144.git.grive@u256.net/", "project": { "id": 47, "url": "http://patchwork.ozlabs.org/api/projects/47/?format=api", "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": "<bea14ca839b11729e634fddf14aa345cd57158fd.1631094144.git.grive@u256.net>", "list_archive_url": null, "date": "2021-09-08T09:47:33", "name": "[ovs-dev,v5,09/27] mov-avg: Add a moving average helper structure", "commit_ref": "9ac3d951b4885986775a2de9626befcafac1f11d", "pull_url": null, "state": "accepted", "archived": false, "hash": "779fd5b8a66ff4c063973b549c39caf76cf33e0b", "submitter": { "id": 78795, "url": "http://patchwork.ozlabs.org/api/people/78795/?format=api", "name": "Gaetan Rivet", "email": "grive@u256.net" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/openvswitch/patch/bea14ca839b11729e634fddf14aa345cd57158fd.1631094144.git.grive@u256.net/mbox/", "series": [ { "id": 261424, "url": "http://patchwork.ozlabs.org/api/series/261424/?format=api", "web_url": "http://patchwork.ozlabs.org/project/openvswitch/list/?series=261424", "date": "2021-09-08T09:47:24", "name": "dpif-netdev: Parallel offload processing", "version": 5, "mbox": "http://patchwork.ozlabs.org/series/261424/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/1525719/comments/", "check": "success", "checks": "http://patchwork.ozlabs.org/api/patches/1525719/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\tdkim=fail reason=\"signature verification failed\" (2048-bit key;\n unprotected) header.d=u256.net header.i=@u256.net header.a=rsa-sha256\n header.s=fm2 header.b=RIzw+32F;\n\tdkim=fail reason=\"signature verification failed\" (2048-bit key;\n unprotected) header.d=messagingengine.com header.i=@messagingengine.com\n header.a=rsa-sha256 header.s=fm3 header.b=FFlSltnz;\n\tdkim-atps=neutral", "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>)", "smtp1.osuosl.org (amavisd-new);\n dkim=pass (2048-bit key) header.d=u256.net header.b=\"RIzw+32F\";\n dkim=pass (2048-bit key) header.d=messagingengine.com\n header.b=\"FFlSltnz\"" ], "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 ozlabs.org (Postfix) with ESMTPS id 4H4HQc24Zjz9sW8\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 8 Sep 2021 19:48:56 +1000 (AEST)", "from localhost (localhost [127.0.0.1])\n\tby smtp4.osuosl.org (Postfix) with ESMTP id 745C4406F6;\n\tWed, 8 Sep 2021 09:48:54 +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 n7975k1-QNkx; Wed, 8 Sep 2021 09:48:53 +0000 (UTC)", "from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56])\n\tby smtp4.osuosl.org (Postfix) with ESMTPS id 8037C424FD;\n\tWed, 8 Sep 2021 09:48:52 +0000 (UTC)", "from lf-lists.osuosl.org (localhost [127.0.0.1])\n\tby lists.linuxfoundation.org (Postfix) with ESMTP id 56CE6C001D;\n\tWed, 8 Sep 2021 09:48:52 +0000 (UTC)", "from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])\n by lists.linuxfoundation.org (Postfix) with ESMTP id 27D9FC0020\n for <ovs-dev@openvswitch.org>; Wed, 8 Sep 2021 09:48:51 +0000 (UTC)", "from localhost (localhost [127.0.0.1])\n by smtp1.osuosl.org (Postfix) with ESMTP id 492888316A\n for <ovs-dev@openvswitch.org>; Wed, 8 Sep 2021 09:48:21 +0000 (UTC)", "from smtp1.osuosl.org ([127.0.0.1])\n by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)\n with ESMTP id gMp1bHut-52o for <ovs-dev@openvswitch.org>;\n Wed, 8 Sep 2021 09:48:18 +0000 (UTC)", "from wout3-smtp.messagingengine.com (wout3-smtp.messagingengine.com\n [64.147.123.19])\n by smtp1.osuosl.org (Postfix) with ESMTPS id 620D1833A3\n for <ovs-dev@openvswitch.org>; Wed, 8 Sep 2021 09:48:16 +0000 (UTC)", "from compute2.internal (compute2.nyi.internal [10.202.2.42])\n by mailout.west.internal (Postfix) with ESMTP id CAC5132009D0;\n Wed, 8 Sep 2021 05:48:15 -0400 (EDT)", "from mailfrontend2 ([10.202.2.163])\n by compute2.internal (MEProxy); Wed, 08 Sep 2021 05:48:16 -0400", "by mail.messagingengine.com (Postfix) with ESMTPA; Wed,\n 8 Sep 2021 05:48:14 -0400 (EDT)" ], "X-Virus-Scanned": [ "amavisd-new at osuosl.org", "amavisd-new at osuosl.org" ], "X-Greylist": "from auto-whitelisted by SQLgrey-1.8.0", "DKIM-Signature": [ "v=1; a=rsa-sha256; c=relaxed/relaxed; d=u256.net; h=from\n :to:cc:subject:date:message-id:in-reply-to:references\n :mime-version:content-transfer-encoding; s=fm2; bh=eYyeK7EYU1+yj\n lHNRMBihR8v6scnY4/NEZoLctkd8LM=; b=RIzw+32Ffj5IsJbow3tQHp5DVUdDC\n Uf/yrcW+1LD7I6qeQWyrEPQ/K9VTlMNkVjg2VJUDW3Hj9a72aeFqM2BXRU7SzkJ4\n cDEg6u0bESO3AFeevGr6z3Dd3EUh8pHZUlY1VCq8OkCv83QS/x+7SKMOEjBoX4Wz\n wcGl806KBcGDN5fSP2JUi4tAMuTkc+dRMkCYADq8IA38ZztnJmz6D1aA6CYRQHfE\n uoAiCed2vXzDkokty+7GFqSlocSM1Et+qVca/7s04y329VmNzcxKUedUrPLrHZmx\n m4I5ZPKRn2H/ineddEAzRwUdBP8WK4jth/Z94QRiyXdQpvce/ZPxqZbow==", "v=1; a=rsa-sha256; c=relaxed/relaxed; d=\n messagingengine.com; h=cc:content-transfer-encoding:date:from\n :in-reply-to:message-id:mime-version:references:subject:to\n :x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=\n fm3; bh=eYyeK7EYU1+yjlHNRMBihR8v6scnY4/NEZoLctkd8LM=; b=FFlSltnz\n 1KRaxkIJeyO+C5qcx536i8Yd5fiw1YDyqdiCLAc/3dHEWDd72POVTuzJhyW2GhO+\n bZhgcnBNTMduwuYrnujppqmuuXP5oRzYcAoAyVezRwFHurK++Vw8y7fzBbD9vhWS\n z/pO4kjdDsoFmvtX62Nxr4FXckatxaQxtSzng6DiC53eZbAD9EtdNcYohXUfMfgv\n 3yRk8xD+5XATeM4kCcF9Pb9sAv+bYOHDMgHZHW26dCzWg/mEhrNa0rexrkSrvS8m\n z/Yusw0bBOHvpm74iqoYE0PDBuEzhFn8wnuRFW9TrV0I011beKvA/DaZc32NWNro\n SGNLiLM1AUyKvA==" ], "X-ME-Sender": "<xms:34Y4YYDersqJX-6sMn2Aatr1B05Q_CsxWF9uWkPEDQvfD463Nmlwtw>\n <xme:34Y4YajYUc7UNFEums73Q0UlYtSc99ZPP_RTLXiPmdIcCXaKs35hCv3wzi8AOKjGh\n SSFWJlhYwIE8JLyh8U>", "X-ME-Received": "\n <xmr:34Y4YbmHwMNXaMPBZnYxGlboMQYEsN0Rmw0D80k1-b_fQgA3HSbgQerkoxbAqFp8_1KBCEiw43_FwIsNDEYIYMoDqw>", "X-ME-Proxy-Cause": "\n gggruggvucftvghtrhhoucdtuddrgedvtddrudefjedgudekucetufdoteggodetrfdotf\n fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen\n uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne\n cujfgurhephffvufffkffojghfggfgsedtkeertdertddtnecuhfhrohhmpefirggvthgr\n nhcutfhivhgvthcuoehgrhhivhgvsehuvdehiedrnhgvtheqnecuggftrfgrthhtvghrnh\n epleegffdttdeftdevhfeikeegveeugeehleeltdduieegvddvveelgeeugeekhffgnecu\n ffhomhgrihhnpegrphgrtghhvgdrohhrghdpfihikhhiphgvughirgdrohhrghenucevlh\n hushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehgrhhivhgvsehu\n vdehiedrnhgvth", "X-ME-Proxy": "<xmx:34Y4YexrWSRcvhwCiBHlR35tYMq-CLx-6ErONgB5UnnoUT-DZ3-1og>\n <xmx:34Y4YdS_3DIIBEBbXARv68KCGCoTPTmmwa-mAP_bvqTUIfOP-rD2fQ>\n <xmx:34Y4YZbBrCx_uXjG1RAasaXIB9nLt5PVs8cKNqR-g5Guu6CVm9UMeQ>\n <xmx:34Y4YcKIAYJ3q6O0GlfzE3ZRJ211CRVc5ZLeArRDxYmwhhZaixVdoQ>", "From": "Gaetan Rivet <grive@u256.net>", "To": "ovs-dev@openvswitch.org", "Date": "Wed, 8 Sep 2021 11:47:33 +0200", "Message-Id": "\n <bea14ca839b11729e634fddf14aa345cd57158fd.1631094144.git.grive@u256.net>", "X-Mailer": "git-send-email 2.31.1", "In-Reply-To": "<cover.1631094144.git.grive@u256.net>", "References": "<cover.1631094144.git.grive@u256.net>", "MIME-Version": "1.0", "Cc": "Eli Britstein <elibr@nvidia.com>,\n Maxime Coquelin <maxime.coquelin@redhat.com>", "Subject": "[ovs-dev] [PATCH v5 09/27] mov-avg: Add a moving average helper\n\tstructure", "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": "Add a new module offering a helper to compute the Cumulative\nMoving Average (CMA) and the Exponential Moving Average (EMA)\nof a series of values.\n\nUse the new helpers to add latency metrics in dpif-netdev.\n\nSigned-off-by: Gaetan Rivet <grive@u256.net>\nReviewed-by: Eli Britstein <elibr@nvidia.com>\nReviewed-by: Maxime Coquelin <maxime.coquelin@redhat.com>\n---\n lib/automake.mk | 1 +\n lib/mov-avg.h | 171 ++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 172 insertions(+)\n create mode 100644 lib/mov-avg.h", "diff": "diff --git a/lib/automake.mk b/lib/automake.mk\nindex 46f869a33..804c8da6f 100644\n--- a/lib/automake.mk\n+++ b/lib/automake.mk\n@@ -179,6 +179,7 @@ lib_libopenvswitch_la_SOURCES = \\\n \tlib/memory.c \\\n \tlib/memory.h \\\n \tlib/meta-flow.c \\\n+\tlib/mov-avg.h \\\n \tlib/multipath.c \\\n \tlib/multipath.h \\\n \tlib/namemap.c \\\ndiff --git a/lib/mov-avg.h b/lib/mov-avg.h\nnew file mode 100644\nindex 000000000..36a6ceb76\n--- /dev/null\n+++ b/lib/mov-avg.h\n@@ -0,0 +1,171 @@\n+/*\n+ * Copyright (c) 2021 NVIDIA Corporation.\n+ *\n+ * Licensed under the Apache License, Version 2.0 (the \"License\");\n+ * you may not use this file except in compliance with the License.\n+ * You may obtain a copy of the License at:\n+ *\n+ * http://www.apache.org/licenses/LICENSE-2.0\n+ *\n+ * Unless required by applicable law or agreed to in writing, software\n+ * distributed under the License is distributed on an \"AS IS\" BASIS,\n+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+ * See the License for the specific language governing permissions and\n+ * limitations under the License.\n+ */\n+\n+#ifndef _MOV_AVG_H\n+#define _MOV_AVG_H 1\n+\n+#include <math.h>\n+\n+/* Moving average helpers. */\n+\n+/* Cumulative Moving Average.\n+ *\n+ * Computes the arithmetic mean over a whole series of value.\n+ * Online equivalent of sum(V) / len(V).\n+ *\n+ * As all values have equal weight, this average will\n+ * be slow to show recent changes in the series.\n+ *\n+ */\n+\n+struct mov_avg_cma {\n+ unsigned long long int count;\n+ double mean;\n+ double sum_dsquared;\n+};\n+\n+#define MOV_AVG_CMA_INITIALIZER \\\n+ { .count = 0, .mean = .0, .sum_dsquared = .0 }\n+\n+static inline void\n+mov_avg_cma_init(struct mov_avg_cma *cma)\n+{\n+ *cma = (struct mov_avg_cma) MOV_AVG_CMA_INITIALIZER;\n+}\n+\n+static inline void\n+mov_avg_cma_update(struct mov_avg_cma *cma, double new_val)\n+{\n+ double new_mean;\n+\n+ cma->count++;\n+ new_mean = cma->mean + (new_val - cma->mean) / cma->count;\n+\n+ cma->sum_dsquared += (new_val - new_mean) * (new_val - cma->mean);\n+ cma->mean = new_mean;\n+}\n+\n+static inline double\n+mov_avg_cma(struct mov_avg_cma *cma)\n+{\n+ return cma->mean;\n+}\n+\n+static inline double\n+mov_avg_cma_std_dev(struct mov_avg_cma *cma)\n+{\n+ double variance = 0.0;\n+\n+ if (cma->count > 1) {\n+ variance = cma->sum_dsquared / (cma->count - 1);\n+ }\n+\n+ return sqrt(variance);\n+}\n+\n+/* Exponential Moving Average.\n+ *\n+ * Each value in the series has an exponentially decreasing weight,\n+ * the older they get the less weight they have.\n+ *\n+ * The smoothing factor 'alpha' must be within 0 < alpha < 1.\n+ * The closer this factor to zero, the more equal the weight between\n+ * recent and older values. As it approaches one, the more recent values\n+ * will have more weight.\n+ *\n+ * The EMA can be thought of as an estimator for the next value when measures\n+ * are dependent. In this case, it can make sense to consider the mean square\n+ * error of the prediction. An 'alpha' minimizing this error would be the\n+ * better choice to improve the estimation.\n+ *\n+ * A common way to choose 'alpha' is to use the following formula:\n+ *\n+ * a = 2 / (N + 1)\n+ *\n+ * With this 'alpha', the EMA will have the same 'center of mass' as an\n+ * equivalent N-values Simple Moving Average.\n+ *\n+ * When using this factor, the N last values of the EMA will have a sum weight\n+ * converging toward 0.8647, meaning that those values will account for 86% of\n+ * the average[1].\n+ *\n+ * [1] https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average\n+ */\n+\n+struct mov_avg_ema {\n+ double alpha; /* 'Smoothing' factor. */\n+ double mean;\n+ double variance;\n+ bool initialized;\n+};\n+\n+/* Choose alpha explicitly. */\n+#define MOV_AVG_EMA_INITIALIZER_ALPHA(a) { \\\n+ .initialized = false, \\\n+ .alpha = (a), .variance = 0.0, .mean = 0.0 \\\n+}\n+\n+/* Choose alpha to consider 'N' past periods as 86% of the EMA. */\n+#define MOV_AVG_EMA_INITIALIZER(n_elem) \\\n+ MOV_AVG_EMA_INITIALIZER_ALPHA(2.0 / ((double)(n_elem) + 1.0))\n+\n+static inline void\n+mov_avg_ema_init_alpha(struct mov_avg_ema *ema,\n+ double alpha)\n+{\n+ *ema = (struct mov_avg_ema) MOV_AVG_EMA_INITIALIZER_ALPHA(alpha);\n+}\n+\n+static inline void\n+mov_avg_ema_init(struct mov_avg_ema *ema,\n+ unsigned long long int n_elem)\n+{\n+ *ema = (struct mov_avg_ema) MOV_AVG_EMA_INITIALIZER(n_elem);\n+}\n+\n+static inline void\n+mov_avg_ema_update(struct mov_avg_ema *ema, double new_val)\n+{\n+ const double alpha = ema->alpha;\n+ double alpha_diff;\n+ double diff;\n+\n+ if (!ema->initialized) {\n+ ema->initialized = true;\n+ ema->mean = new_val;\n+ return;\n+ }\n+\n+ diff = new_val - ema->mean;\n+ alpha_diff = alpha * diff;\n+\n+ ema->variance = (1.0 - alpha) * (ema->variance + alpha_diff * diff);\n+ ema->mean = ema->mean + alpha_diff;\n+}\n+\n+static inline double\n+mov_avg_ema(struct mov_avg_ema *ema)\n+{\n+ return ema->mean;\n+}\n+\n+static inline double\n+mov_avg_ema_std_dev(struct mov_avg_ema *ema)\n+{\n+ return sqrt(ema->variance);\n+}\n+\n+#endif /* _MOV_AVG_H */\n", "prefixes": [ "ovs-dev", "v5", "09/27" ] }