Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/55584/?format=api
{ "id": 55584, "url": "http://patches.dpdk.org/api/patches/55584/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/20190628090124.16849-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": "<20190628090124.16849-2-mattias.ronnblom@ericsson.com>", "list_archive_url": "https://inbox.dpdk.org/dev/20190628090124.16849-2-mattias.ronnblom@ericsson.com", "date": "2019-06-28T09:01:20", "name": "[v4,1/5] eal: replace libc-based random number generation with LFSR", "commit_ref": null, "pull_url": null, "state": "accepted", "archived": true, "hash": "7e6374c36ecf4689c117ab48aee741f6d3a37490", "submitter": { "id": 1077, "url": "http://patches.dpdk.org/api/people/1077/?format=api", "name": "Mattias Rönnblom", "email": "mattias.ronnblom@ericsson.com" }, "delegate": null, "mbox": "http://patches.dpdk.org/project/dpdk/patch/20190628090124.16849-2-mattias.ronnblom@ericsson.com/mbox/", "series": [ { "id": 5220, "url": "http://patches.dpdk.org/api/series/5220/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=5220", "date": "2019-06-28T09:01:20", "name": "Pseudo-random number generation improvements", "version": 4, "mbox": "http://patches.dpdk.org/series/5220/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/55584/comments/", "check": "warning", "checks": "http://patches.dpdk.org/api/patches/55584/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 4F9141B99A;\n\tFri, 28 Jun 2019 11:01:31 +0200 (CEST)", "from sesbmg22.ericsson.net (sesbmg22.ericsson.net [193.180.251.48])\n\tby dpdk.org (Postfix) with ESMTP id 263C24C6C\n\tfor <dev@dpdk.org>; Fri, 28 Jun 2019 11:01:30 +0200 (CEST)", "from ESESSMB504.ericsson.se (Unknown_Domain [153.88.183.122])\n\tby sesbmg22.ericsson.net (Symantec Mail Security) with SMTP id\n\tCD.97.06164.967D51D5; Fri, 28 Jun 2019 11:01:29 +0200 (CEST)", "from ESESBMB503.ericsson.se (153.88.183.170) by\n\tESESSMB504.ericsson.se (153.88.183.122) 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; Fri, 28 Jun 2019 11:01:29 +0200", "from selio1a020.lmera.ericsson.se (153.88.183.153) by\n\tsmtp.internal.ericsson.com (153.88.183.186) with Microsoft SMTP\n\tServer id\n\t15.1.1713.5 via Frontend Transport; Fri, 28 Jun 2019 11:01:29 +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\tx5S91SYV019342; Fri, 28 Jun 2019 11:01:29 +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=1561712489; x=1564304489;\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=+jqqRp1ZocOB69gs+FBWdnMQ0sOqM8XEJhNaVIhZLx8=;\n\tb=Ejacjh37rpj3+kF61u24QiMguA4EGCxD3NL4Xz+2HfFJB0HfK/V9BxjTT3GlpnXN\n\t74DH/xmT0M3Z5aq0Rl+RDsUvSGSLDmcOVUQu4q8Vp1PWCzlDkPXXi18wYqilLIoR\n\t4w1D/hzY0iqXLxWwV234fW7BVSrKjT2OVf6Va75lLgw=;", "X-AuditID": "c1b4fb30-6ddff70000001814-7f-5d15d7697883", "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<thomas@monjalon.net>, =?utf-8?q?Mattias_R=C3=B6nnblom?=\n\t<mattias.ronnblom@ericsson.com>", "Date": "Fri, 28 Jun 2019 11:01:20 +0200", "Message-ID": "<20190628090124.16849-2-mattias.ronnblom@ericsson.com>", "X-Mailer": "git-send-email 2.17.1", "In-Reply-To": "<20190628090124.16849-1-mattias.ronnblom@ericsson.com>", "References": "<20190605104400.24484-1-mattias.ronnblom@ericsson.com>\n\t<20190628090124.16849-1-mattias.ronnblom@ericsson.com>", "MIME-Version": "1.0", "Content-Type": "text/plain; charset=\"UTF-8\"", "Content-Transfer-Encoding": "8bit", "X-Brightmail-Tracker": "H4sIAAAAAAAAA+NgFvrKLMWRmVeSWpSXmKPExsUyM2J7lW7mddFYg+5eHYsbq+wttq/oYrN4\n\t92k7k8Wt5pNsFovvyFl8enCCxYHN49eCpawei/e8ZPI4dnMau0fPyXlMHu/3XWXzuPJ9NWMA\n\tWxSXTUpqTmZZapG+XQJXxq5ld5kL5oZUrJ73kaWB8Z9rFyMnh4SAicTOrsVMXYxcHEICRxkl\n\t9kxZzw7hfGOUeHTwJFTmIqPE0U3TGEFahAQuM0oc354LYrMJeEpMftfNAmKLCAhJLP14Gayb\n\tWeAao8TXSy+YQRLCAkESR5+dBCtiEVCVWPxkPhOIzSvgJPG2aQsrxB3yEqs3HACr5xRwluha\n\t28sOsaxa4ueJh2wQ9YISJ2c+AZvDLKAp0br9NzuELS/RvHU2M0S9lsT9JV+YJzAKzULSMgtJ\n\tyywkLQsYmVcxihanFiflphsZ6aUWZSYXF+fn6eWllmxiBEbGwS2/DXYwvnzueIhRgINRiYd3\n\twR7RWCHWxLLiytxDjBIczEoivJLnRGKFeFMSK6tSi/Lji0pzUosPMUpzsCiJ8673/hcjJJCe\n\tWJKanZpakFoEk2Xi4JRqYAyoS0q3eLA/xHana5mHs8z+yScTrwjqXFt/3u2J17vLmXcqp4g5\n\tycTHKCWLmygFzPHNdteRvetzRHJyzOlzLhekimMFk7/3/PVclPy96W+258PZAQUc209c+mF+\n\thDOD76hD8/sAjY6s1x+ceLl3uzLY54SEXPj7nV3ou62Kht02Scel+sXuSizFGYmGWsxFxYkA\n\teEfTnIgCAAA=", "Subject": "[dpdk-dev] [PATCH v4 1/5] 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>\nAcked-by: Bruce Richardson <bruce.richardson@intel.com>\n---\n MAINTAINERS | 5 +\n doc/guides/rel_notes/release_19_08.rst | 9 ++\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 | 2 +\n 10 files changed, 169 insertions(+), 22 deletions(-)\n create mode 100644 lib/librte_eal/common/rte_random.c", "diff": "diff --git a/MAINTAINERS b/MAINTAINERS\nindex 0c3b48920..75775129d 100644\n--- a/MAINTAINERS\n+++ b/MAINTAINERS\n@@ -227,6 +227,11 @@ M: Joyce Kong <joyce.kong@arm.com>\n F: lib/librte_eal/common/include/generic/rte_ticketlock.h\n F: app/test/test_ticketlock.c\n \n+Pseudo-random Number Generation\n+M: Mattias Rönnblom <mattias.ronnblom@ericsson.com>\n+F: lib/librte_eal/common/include/rte_random.h\n+F: lib/librte_eal/common/rte_random.c\n+\n ARM v7\n M: Jan Viktorin <viktorin@rehivetech.com>\n M: Gavin Hu <gavin.hu@arm.com>\ndiff --git a/doc/guides/rel_notes/release_19_08.rst b/doc/guides/rel_notes/release_19_08.rst\nindex 3da266705..7080d1f47 100644\n--- a/doc/guides/rel_notes/release_19_08.rst\n+++ b/doc/guides/rel_notes/release_19_08.rst\n@@ -99,6 +99,15 @@ New Features\n Updated ``librte_telemetry`` to fetch the global metrics from the\n ``librte_metrics`` library.\n \n+* **Updated the EAL Pseudo-random Number Generator.**\n+\n+ The lrand48()-based rte_rand() function is replaced with a\n+ DPDK-native combined Linear Feedback Shift Register (LFSR)\n+ pseudo-random number generator (PRNG).\n+\n+ This new PRNG implementation is multi-thread safe, provides\n+ higher-quality pseudo-random numbers (including full 64 bit\n+ support) and improved performance.\n \n Removed Items\n -------------\ndiff --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 97633a55a..3ccc5503c 100644\n--- a/lib/librte_eal/freebsd/eal/eal.c\n+++ b/lib/librte_eal/freebsd/eal/eal.c\n@@ -758,8 +758,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 d96ed3a7c..5f2083c4b 100644\n--- a/lib/librte_eal/linux/eal/eal.c\n+++ b/lib/librte_eal/linux/eal/eal.c\n@@ -1122,8 +1122,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 824edf0ff..20c1a9018 100644\n--- a/lib/librte_eal/rte_eal_version.map\n+++ b/lib/librte_eal/rte_eal_version.map\n@@ -292,6 +292,8 @@ DPDK_19.08 {\n \n \trte_lcore_index;\n \trte_lcore_to_socket_id;\n+\trte_rand;\n+\trte_srand;\n \n } DPDK_19.05;\n \n", "prefixes": [ "v4", "1/5" ] }