Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/53394/?format=api
{ "id": 53394, "url": "http://patches.dpdk.org/api/patches/53394/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/20190514092046.30808-2-mattias.ronnblom@ericsson.com/", "project": { "id": 1, "url": "http://patches.dpdk.org/api/projects/1/?format=api", "name": "DPDK", "link_name": "dpdk", "list_id": "dev.dpdk.org", "list_email": "dev@dpdk.org", "web_url": "http://core.dpdk.org", "scm_url": "git://dpdk.org/dpdk", "webscm_url": "http://git.dpdk.org/dpdk", "list_archive_url": "https://inbox.dpdk.org/dev", "list_archive_url_format": "https://inbox.dpdk.org/dev/{}", "commit_url_format": "" }, "msgid": "<20190514092046.30808-2-mattias.ronnblom@ericsson.com>", "list_archive_url": "https://inbox.dpdk.org/dev/20190514092046.30808-2-mattias.ronnblom@ericsson.com", "date": "2019-05-14T09:20:41", "name": "[1/6] eal: replace libc-based random number generation with LFSR", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "2fb76fcf75738d706031606dcde685bf62b6da25", "submitter": { "id": 1077, "url": "http://patches.dpdk.org/api/people/1077/?format=api", "name": "Mattias Rönnblom", "email": "mattias.ronnblom@ericsson.com" }, "delegate": { "id": 1, "url": "http://patches.dpdk.org/api/users/1/?format=api", "username": "tmonjalo", "first_name": "Thomas", "last_name": "Monjalon", "email": "thomas@monjalon.net" }, "mbox": "http://patches.dpdk.org/project/dpdk/patch/20190514092046.30808-2-mattias.ronnblom@ericsson.com/mbox/", "series": [ { "id": 4650, "url": "http://patches.dpdk.org/api/series/4650/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=4650", "date": "2019-05-14T09:20:40", "name": "Pseudo-random number generation improvements", "version": 1, "mbox": "http://patches.dpdk.org/series/4650/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/53394/comments/", "check": "fail", "checks": "http://patches.dpdk.org/api/patches/53394/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@dpdk.org", "Delivered-To": "patchwork@dpdk.org", "Received": [ "from [92.243.14.124] (localhost [127.0.0.1])\n\tby dpdk.org (Postfix) with ESMTP id 8E96C5B2A;\n\tTue, 14 May 2019 11:21:34 +0200 (CEST)", "from sessmg22.ericsson.net (sessmg22.ericsson.net [193.180.251.58])\n\tby dpdk.org (Postfix) with ESMTP id 9DB1A5A4A\n\tfor <dev@dpdk.org>; Tue, 14 May 2019 11:21:33 +0200 (CEST)", "from ESESBMB503.ericsson.se (Unknown_Domain [153.88.183.116])\n\tby sessmg22.ericsson.net (Symantec Mail Security) with SMTP id\n\t65.2B.06303.D988ADC5; Tue, 14 May 2019 11:21:33 +0200 (CEST)", "from ESESBMB502.ericsson.se (153.88.183.169) by\n\tESESBMB503.ericsson.se (153.88.183.170) with Microsoft SMTP Server\n\t(version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id\n\t15.1.1713.5; Tue, 14 May 2019 11:21:32 +0200", "from selio1a020.lmera.ericsson.se (153.88.183.153) by\n\tsmtp.internal.ericsson.com (153.88.183.185) with Microsoft SMTP\n\tServer id\n\t15.1.1713.5 via Frontend Transport; Tue, 14 May 2019 11:21:32 +0200", "from breslau.lmera.ericsson.se (breslau.lmera.ericsson.se\n\t[150.132.109.241])\n\tby selio1a020.lmera.ericsson.se (8.15.1+Sun/8.15.1) with ESMTP id\n\tx4E9LQN5027252; Tue, 14 May 2019 11:21:32 +0200 (CEST)" ], "DKIM-Signature": "v=1; a=rsa-sha256; d=ericsson.com; s=mailgw201801;\n\tc=relaxed/relaxed; \n\tq=dns/txt; i=@ericsson.com; t=1557825693; x=1560417693;\n\th=From:Sender:Reply-To:Subject:Date:Message-ID:To:CC:MIME-Version:Content-Type:\n\tContent-Transfer-Encoding:Content-ID:Content-Description:Resent-Date:Resent-From:\n\tResent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To:References:List-Id:\n\tList-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive;\n\tbh=d8IrLP7hWL5S+xfzhDw/zKwOPIKdITQcZEqq2N7axeU=;\n\tb=OKy7gGNqpahmLT9bF7jTec2CocPjHyXq7S5Wnus+i0jDMz2oAYb/cF5IDKAzrwfa\n\ttCP+MKT/6rnMZATf9u+c8U6B65qMnfN8VHfaLB/srj9KCIV1aUYGmQTOlWo6Io/A\n\ttnS9z2eiy3nqaLoQoYSr3INsFta5MlDDrHwBdd5M7mE=;", "X-AuditID": "c1b4fb3a-709ff7000000189f-9b-5cda889d804c", "From": "=?utf-8?q?Mattias_R=C3=B6nnblom?= <mattias.ronnblom@ericsson.com>", "To": "<dev@dpdk.org>", "CC": "<nhorman@tuxdriver.com>, <stephen@networkplumber.org>,\n\t<david.marchand@redhat.com>, <bruce.richardson@intel.com>, \n\t=?utf-8?q?Mattias_R=C3=B6nnblom?= <mattias.ronnblom@ericsson.com>", "Date": "Tue, 14 May 2019 11:20:41 +0200", "Message-ID": "<20190514092046.30808-2-mattias.ronnblom@ericsson.com>", "X-Mailer": "git-send-email 2.17.1", "In-Reply-To": "<20190514092046.30808-1-mattias.ronnblom@ericsson.com>", "References": "<20190508181014.7dde7580@xps13>\n\t<20190514092046.30808-1-mattias.ronnblom@ericsson.com>", "MIME-Version": "1.0", "Content-Type": "text/plain; charset=\"UTF-8\"", "Content-Transfer-Encoding": "8bit", "X-Brightmail-Tracker": "H4sIAAAAAAAAA+NgFnrJLMWRmVeSWpSXmKPExsUyM2J7ie7cjlsxBpd381rcWGVvsX1FF5vF\n\tu0/bmSxuNZ9ks1h8R86B1ePXgqWsHov3vGTy6Dk5j8nj/b6rbB5Xvq9mDGCN4rJJSc3JLEst\n\t0rdL4MpY93Y2e8F7j4rDC0QaGLfbdDFycEgImEgce2PcxcjFISRwlFGiefl8FgjnG6PErfUf\n\t2CGci4wSrz4eYYVwLjNKTG/7A1TGycEm4Ckx+V03mC0iICSx9ONlsA5mgb1AHevmgSWEBfwl\n\tlvz7wwqyj0VAVWLn2WqQMK+Ak8Tjq2dYQWwJAXmJ1RsOMIPYnALOEpOm3GIHsYUEUiT+9Dxi\n\tgagXlDg58wmYzSygKdG6/Tc7hC0v0bx1NjNEvZbE/SVfmCcwCs1C0jILScssJC0LGJlXMYoW\n\tpxYX56YbGemlFmUmFxfn5+nlpZZsYgRGwMEtv612MB587niIUYCDUYmHNzb9VowQa2JZcWXu\n\tIUYJDmYlEd4oxRsxQrwpiZVVqUX58UWlOanFhxilOViUxHmjV++JERJITyxJzU5NLUgtgsky\n\tcXBKNTBm1ulfOlg/TSRblGtp8O2MVd8zcnZO5A621YsqKmcU2KP/jMt8mlDGRSGZ7a7P8njj\n\tJqXutXXY3qu0wvLTzo2Ptykfe94izPQ7+kv03kc3xR/8eujlUNmk8NU2Sfeu76bz26Y49VS7\n\tS551mhMZyXNul/2kdeHiVz/9nMW5NVihVMZk7ektZxKUWIozEg21mIuKEwHXCbS+fAIAAA==", "Subject": "[dpdk-dev] [PATCH 1/6] eal: replace libc-based random number\n\tgeneration with LFSR", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.15", "Precedence": "list", "List-Id": "DPDK patches and discussions <dev.dpdk.org>", "List-Unsubscribe": "<https://mails.dpdk.org/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>", "List-Archive": "<http://mails.dpdk.org/archives/dev/>", "List-Post": "<mailto:dev@dpdk.org>", "List-Help": "<mailto:dev-request@dpdk.org?subject=help>", "List-Subscribe": "<https://mails.dpdk.org/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "This commit replaces rte_rand()'s use of lrand48() with a DPDK-native\ncombined Linear Feedback Shift Register (LFSR) (also known as\nTausworthe) pseudo-random number generator.\n\nThis generator is faster and produces better-quality random numbers\nthan the linear congruential generator (LCG) of lib's lrand48(). The\nimplementation, as opposed to lrand48(), is multi-thread safe in\nregards to concurrent rte_rand() calls from different lcore threads.\nA LCG is still used, but only to seed the five per-lcore LFSR\nsequences.\n\nIn addition, this patch also addresses the issue of the legacy\nimplementation only producing 62 bits of pseudo randomness, while the\nAPI requires all 64 bits to be random.\n\nThis pseudo-random number generator is not cryptographically secure -\njust like lrand48().\n\nBugzilla ID: 114\nBugzilla ID: 276\n\nSigned-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>\n---\n lib/librte_eal/common/include/rte_random.h | 29 ++---\n lib/librte_eal/common/meson.build | 1 +\n lib/librte_eal/common/rte_random.c | 139 +++++++++++++++++++++\n lib/librte_eal/freebsd/eal/Makefile | 1 +\n lib/librte_eal/freebsd/eal/eal.c | 2 -\n lib/librte_eal/linux/eal/Makefile | 1 +\n lib/librte_eal/linux/eal/eal.c | 2 -\n lib/librte_eal/rte_eal_version.map | 8 ++\n 8 files changed, 161 insertions(+), 22 deletions(-)\n create mode 100644 lib/librte_eal/common/rte_random.c", "diff": "diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h\nindex b2ca1c209..66dfe8ae7 100644\n--- a/lib/librte_eal/common/include/rte_random.h\n+++ b/lib/librte_eal/common/include/rte_random.h\n@@ -16,7 +16,6 @@ extern \"C\" {\n #endif\n \n #include <stdint.h>\n-#include <stdlib.h>\n \n /**\n * Seed the pseudo-random generator.\n@@ -25,34 +24,28 @@ extern \"C\" {\n * value. It may need to be re-seeded by the user with a real random\n * value.\n *\n+ * This function is not multi-thread safe in regards to other\n+ * rte_srand() calls, nor is it in relation to concurrent rte_rand()\n+ * calls.\n+ *\n * @param seedval\n * The value of the seed.\n */\n-static inline void\n-rte_srand(uint64_t seedval)\n-{\n-\tsrand48((long)seedval);\n-}\n+void\n+rte_srand(uint64_t seedval);\n \n /**\n * Get a pseudo-random value.\n *\n- * This function generates pseudo-random numbers using the linear\n- * congruential algorithm and 48-bit integer arithmetic, called twice\n- * to generate a 64-bit value.\n+ * The generator is not cryptographically secure.\n+ *\n+ * If called from lcore threads, this function is thread-safe.\n *\n * @return\n * A pseudo-random value between 0 and (1<<64)-1.\n */\n-static inline uint64_t\n-rte_rand(void)\n-{\n-\tuint64_t val;\n-\tval = (uint64_t)lrand48();\n-\tval <<= 32;\n-\tval += (uint64_t)lrand48();\n-\treturn val;\n-}\n+uint64_t\n+rte_rand(void);\n \n #ifdef __cplusplus\n }\ndiff --git a/lib/librte_eal/common/meson.build b/lib/librte_eal/common/meson.build\nindex 0670e4102..bafd23207 100644\n--- a/lib/librte_eal/common/meson.build\n+++ b/lib/librte_eal/common/meson.build\n@@ -35,6 +35,7 @@ common_sources = files(\n \t'rte_keepalive.c',\n \t'rte_malloc.c',\n \t'rte_option.c',\n+\t'rte_random.c',\n \t'rte_reciprocal.c',\n \t'rte_service.c'\n )\ndiff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c\nnew file mode 100644\nindex 000000000..4d3cf5226\n--- /dev/null\n+++ b/lib/librte_eal/common/rte_random.c\n@@ -0,0 +1,139 @@\n+/* SPDX-License-Identifier: BSD-3-Clause\n+ * Copyright(c) 2019 Ericsson AB\n+ */\n+\n+#include <stdlib.h>\n+\n+#include <rte_branch_prediction.h>\n+#include <rte_cycles.h>\n+#include <rte_eal.h>\n+#include <rte_lcore.h>\n+#include <rte_memory.h>\n+#include <rte_random.h>\n+\n+struct rte_rand_state {\n+\tuint64_t z1;\n+\tuint64_t z2;\n+\tuint64_t z3;\n+\tuint64_t z4;\n+\tuint64_t z5;\n+} __rte_cache_aligned;\n+\n+static struct rte_rand_state rand_states[RTE_MAX_LCORE];\n+\n+static uint32_t\n+__rte_rand_lcg32(uint32_t *seed)\n+{\n+\t*seed = 1103515245U * *seed + 12345U;\n+\n+\treturn *seed;\n+}\n+\n+static uint64_t\n+__rte_rand_lcg64(uint32_t *seed)\n+{\n+\tuint64_t low;\n+\tuint64_t high;\n+\n+\t/* A 64-bit LCG would have been much cleaner, but good\n+\t * multiplier/increments for such seem hard to come by.\n+\t */\n+\n+\tlow = __rte_rand_lcg32(seed);\n+\thigh = __rte_rand_lcg32(seed);\n+\n+\treturn low | (high << 32);\n+}\n+\n+static uint64_t\n+__rte_rand_lfsr258_gen_seed(uint32_t *seed, uint64_t min_value)\n+{\n+\tuint64_t res;\n+\n+\tres = __rte_rand_lcg64(seed);\n+\n+\tif (res < min_value)\n+\t\tres += min_value;\n+\n+\treturn res;\n+}\n+\n+static void\n+__rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)\n+{\n+\tuint32_t lcg_seed;\n+\n+\tlcg_seed = (uint32_t)(seed ^ (seed >> 32));\n+\n+\tstate->z1 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 2UL);\n+\tstate->z2 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 512UL);\n+\tstate->z3 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 4096UL);\n+\tstate->z4 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 131072UL);\n+\tstate->z5 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 8388608UL);\n+}\n+\n+void\n+rte_srand(uint64_t seed)\n+{\n+\tunsigned int lcore_id;\n+\n+\t/* add lcore_id to seed to avoid having the same sequence */\n+\tfor (lcore_id = 0; lcore_id < RTE_MAX_LCORE; lcore_id++)\n+\t\t__rte_srand_lfsr258(seed + lcore_id, &rand_states[lcore_id]);\n+}\n+\n+static __rte_always_inline uint64_t\n+__rte_rand_lfsr258_comp(uint64_t z, uint64_t a, uint64_t b, uint64_t c,\n+\t\t\tuint64_t d)\n+{\n+\treturn ((z & c) << d) ^ (((z << a) ^ z) >> b);\n+}\n+\n+/* Based on L’Ecuyer, P.: Tables of maximally equidistributed combined\n+ * LFSR generators.\n+ */\n+\n+static __rte_always_inline uint64_t\n+__rte_rand_lfsr258(struct rte_rand_state *state)\n+{\n+\tstate->z1 = __rte_rand_lfsr258_comp(state->z1, 1UL, 53UL,\n+\t\t\t\t\t 18446744073709551614UL, 10UL);\n+\tstate->z2 = __rte_rand_lfsr258_comp(state->z2, 24UL, 50UL,\n+\t\t\t\t\t 18446744073709551104UL, 5UL);\n+\tstate->z3 = __rte_rand_lfsr258_comp(state->z3, 3UL, 23UL,\n+\t\t\t\t\t 18446744073709547520UL, 29UL);\n+\tstate->z4 = __rte_rand_lfsr258_comp(state->z4, 5UL, 24UL,\n+\t\t\t\t\t 18446744073709420544UL, 23UL);\n+\tstate->z5 = __rte_rand_lfsr258_comp(state->z5, 3UL, 33UL,\n+\t\t\t\t\t 18446744073701163008UL, 8UL);\n+\n+\treturn state->z1 ^ state->z2 ^ state->z3 ^ state->z4 ^ state->z5;\n+}\n+\n+static __rte_always_inline\n+struct rte_rand_state *__rte_rand_get_state(void)\n+{\n+\tunsigned int lcore_id;\n+\n+\tlcore_id = rte_lcore_id();\n+\n+\tif (unlikely(lcore_id == LCORE_ID_ANY))\n+\t\tlcore_id = rte_get_master_lcore();\n+\n+\treturn &rand_states[lcore_id];\n+}\n+\n+uint64_t\n+rte_rand(void)\n+{\n+\tstruct rte_rand_state *state;\n+\n+\tstate = __rte_rand_get_state();\n+\n+\treturn __rte_rand_lfsr258(state);\n+}\n+\n+RTE_INIT(rte_rand_init)\n+{\n+\trte_srand(rte_get_timer_cycles());\n+}\ndiff --git a/lib/librte_eal/freebsd/eal/Makefile b/lib/librte_eal/freebsd/eal/Makefile\nindex 19854ee2c..ca616c480 100644\n--- a/lib/librte_eal/freebsd/eal/Makefile\n+++ b/lib/librte_eal/freebsd/eal/Makefile\n@@ -69,6 +69,7 @@ SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += malloc_mp.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_keepalive.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_option.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_service.c\n+SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_random.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_reciprocal.c\n \n # from arch dir\ndiff --git a/lib/librte_eal/freebsd/eal/eal.c b/lib/librte_eal/freebsd/eal/eal.c\nindex c6ac9028f..5d43310b3 100644\n--- a/lib/librte_eal/freebsd/eal/eal.c\n+++ b/lib/librte_eal/freebsd/eal/eal.c\n@@ -727,8 +727,6 @@ rte_eal_init(int argc, char **argv)\n #endif\n \t}\n \n-\trte_srand(rte_rdtsc());\n-\n \t/* in secondary processes, memory init may allocate additional fbarrays\n \t * not present in primary processes, so to avoid any potential issues,\n \t * initialize memzones first.\ndiff --git a/lib/librte_eal/linux/eal/Makefile b/lib/librte_eal/linux/eal/Makefile\nindex 6e5261152..729795a10 100644\n--- a/lib/librte_eal/linux/eal/Makefile\n+++ b/lib/librte_eal/linux/eal/Makefile\n@@ -77,6 +77,7 @@ SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += malloc_mp.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_keepalive.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_option.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_service.c\n+SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_random.c\n SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_reciprocal.c\n \n # from arch dir\ndiff --git a/lib/librte_eal/linux/eal/eal.c b/lib/librte_eal/linux/eal/eal.c\nindex 161399619..d6bf0e89e 100644\n--- a/lib/librte_eal/linux/eal/eal.c\n+++ b/lib/librte_eal/linux/eal/eal.c\n@@ -1083,8 +1083,6 @@ rte_eal_init(int argc, char **argv)\n #endif\n \t}\n \n-\trte_srand(rte_rdtsc());\n-\n \tif (rte_eal_log_init(logid, internal_config.syslog_facility) < 0) {\n \t\trte_eal_init_alert(\"Cannot init logging.\");\n \t\trte_errno = ENOMEM;\ndiff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map\nindex 245493461..e615d7cb9 100644\n--- a/lib/librte_eal/rte_eal_version.map\n+++ b/lib/librte_eal/rte_eal_version.map\n@@ -287,6 +287,14 @@ DPDK_19.05 {\n \n } DPDK_18.11;\n \n+DPDK_19.08 {\n+\tglobal:\n+\n+\trte_rand;\n+\trte_srand;\n+\n+} DPDK_19.05;\n+\n EXPERIMENTAL {\n \tglobal:\n \n", "prefixes": [ "1/6" ] }