Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/52968/?format=api
{ "id": 52968, "url": "http://patches.dpdk.org/api/patches/52968/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/20190419212138.17422-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": "<20190419212138.17422-2-mattias.ronnblom@ericsson.com>", "list_archive_url": "https://inbox.dpdk.org/dev/20190419212138.17422-2-mattias.ronnblom@ericsson.com", "date": "2019-04-19T21:21:37", "name": "[RFC,v2,1/2] eal: replace libc-based random number generation with LFSR", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "eddaddec02996c3959131802963a88b6677c712e", "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/20190419212138.17422-2-mattias.ronnblom@ericsson.com/mbox/", "series": [ { "id": 4404, "url": "http://patches.dpdk.org/api/series/4404/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=4404", "date": "2019-04-19T21:21:36", "name": "Pseudo-number generation improvements", "version": 2, "mbox": "http://patches.dpdk.org/series/4404/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/52968/comments/", "check": "success", "checks": "http://patches.dpdk.org/api/patches/52968/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 3F4021BC1F;\n\tFri, 19 Apr 2019 23:21:47 +0200 (CEST)", "from sessmg23.ericsson.net (sessmg23.ericsson.net [193.180.251.45])\n\tby dpdk.org (Postfix) with ESMTP id 6DBD21B9F4\n\tfor <dev@dpdk.org>; Fri, 19 Apr 2019 23:21:43 +0200 (CEST)", "from ESESBMB503.ericsson.se (Unknown_Domain [153.88.183.116])\n\tby sessmg23.ericsson.net (Symantec Mail Security) with SMTP id\n\t20.19.24628.7EB3ABC5; Fri, 19 Apr 2019 23:21:43 +0200 (CEST)", "from ESESBMB501.ericsson.se (153.88.183.168) 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; Fri, 19 Apr 2019 23:21:42 +0200", "from selio1a020.lmera.ericsson.se (153.88.183.153) by\n\tsmtp.internal.ericsson.com (153.88.183.184) with Microsoft SMTP\n\tServer id\n\t15.1.1713.5 via Frontend Transport; Fri, 19 Apr 2019 23:21:42 +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\tx3JLLf28022797; Fri, 19 Apr 2019 23:21:42 +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=1555708903; x=1558300903;\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=U6H9f/buEJEOiuswpr2+r+74zISw0VG/j8aamV7/PsE=;\n\tb=hmUdmlV8BnUF4R6pchuAi1DLwK5Vpto8XHbmp6BN19+WJaZSdRTi25KfnobQF+pF\n\tcLRQLJkz4lbNJhXsIyRehZEXHuJLSnjhScTp/9wh0c1D8cq7Dub69ivrnseTyWOm\n\tQhaeTWRfLaLO9FjN3J6MeOtXdeDLSkESogtN5fVui0E=;", "X-AuditID": "c1b4fb2d-fc5ff70000006034-93-5cba3be72a2d", "From": "=?utf-8?q?Mattias_R=C3=B6nnblom?= <mattias.ronnblom@ericsson.com>", "To": "<dev@dpdk.org>", "CC": "<stephen@networkplumber.org>, =?utf-8?q?Mattias_R=C3=B6nnblom?=\n\t<mattias.ronnblom@ericsson.com>", "Date": "Fri, 19 Apr 2019 23:21:37 +0200", "Message-ID": "<20190419212138.17422-2-mattias.ronnblom@ericsson.com>", "X-Mailer": "git-send-email 2.17.1", "In-Reply-To": "<20190419212138.17422-1-mattias.ronnblom@ericsson.com>", "References": "<20190408123029.6701-1-mattias.ronnblom@ericsson.com>\n\t<20190419212138.17422-1-mattias.ronnblom@ericsson.com>", "MIME-Version": "1.0", "Content-Type": "text/plain; charset=\"UTF-8\"", "Content-Transfer-Encoding": "8bit", "X-Brightmail-Tracker": "H4sIAAAAAAAAA+NgFjrHLMWRmVeSWpSXmKPExsUyM2J7ie5z610xBtOmM1u8+7SdyWLxHTkH\n\tJo9fC5ayevScnMcUwBTFZZOSmpNZllqkb5fAlbHxzAuWggnuFdsnNLI0MM6z7mLk5JAQMJHo\n\t37GAvYuRi0NI4CijxKbpv1ggnG+MEjOf3GCGcC4ySmxv/QXlXGaUWN4/jw2kn03AU2Lyu24W\n\tEFtEQEhi6cfL7CA2s0C6xMbTnUwgtrBAgMSXU2/BalgEVCV2rp7ECmLzCjhJtO5bxwxxh7zE\n\t6g0HwGxOAWeJ9QePgdUICVRJTF3/gAmiXlDi5MwnLBDzNSVat/+G2iUv0bx1NjNEvZbE/SVf\n\tmCcwCs1C0jILScssJC0LGJlXMYoWpxYX56YbGeulFmUmFxfn5+nlpZZsYgSG8sEtv3V3MK5+\n\t7XiIUYCDUYmHV1p9V4wQa2JZcWXuIUYJDmYlEV7HlC0xQrwpiZVVqUX58UWlOanFhxilOViU\n\txHn/CAnGCAmkJ5akZqemFqQWwWSZODilGhiDzUQ6UnJnTpy2wtkuqZLj7Owcw6K3xVuOlO11\n\tYvQO+PP5++/jE/0dKi6c4j03Qy41b/396cty/z4+UWzJ7ZYgqLeikP/Xhf2zToSorujPKPwU\n\tHfjY+Z+LxK7PL+ZYfYx6NmmNzk4LKUc2L9uTbNHnotYwBB9IK9rt8uHk+jTJrIRsj9yQ5mIl\n\tluKMREMt5qLiRAD/ZEyMYQIAAA==", "Subject": "[dpdk-dev] [RFC v2 1/2] 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-number generator, with five sequences.\n\nThis generator is faster and produces better quality random numbers\nthan libc's lrand48() implementation. This implementation, as opposed\nto lrand48(), is multi-thread safe in regards to concurrent rte_rand()\ncalls from different lcore threads. It is not cryptographically\nsecure - just like lrand48().\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 | 137 +++++++++++++++++++++\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 8 files changed, 153 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..288e7b8c5\n--- /dev/null\n+++ b/lib/librte_eal/common/rte_random.c\n@@ -0,0 +1,137 @@\n+/* SPDX-License-Identifier: BSD-3-Clause\n+ * Copyright(c) 2019 Ericsson AB\n+ */\n+\n+#include <stdlib.h>\n+\n+#include <rte_cycles.h>\n+#include <rte_eal.h>\n+#include <rte_lcore.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 well-known\n+\t * good multiplier/increments 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 __rte_experimental\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 __rte_experimental\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 f7ae62d7b..c2bdf0a67 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 d6e375135..0d60668fa 100644\n--- a/lib/librte_eal/rte_eal_version.map\n+++ b/lib/librte_eal/rte_eal_version.map\n@@ -366,10 +366,12 @@ EXPERIMENTAL {\n \trte_mp_request_async;\n \trte_mp_sendmsg;\n \trte_option_register;\n+\trte_rand;\n \trte_realloc_socket;\n \trte_service_lcore_attr_get;\n \trte_service_lcore_attr_reset_all;\n \trte_service_may_be_active;\n \trte_socket_count;\n \trte_socket_id_by_idx;\n+\trte_srand;\n };\n", "prefixes": [ "RFC", "v2", "1/2" ] }