[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Minios-devel] [UNIKRAFT PATCH 3/5] lib/ukswrand: Introduce libukswrand



On 14.06.2018 21:12, Yuri Volchkov wrote:
Reviewed-by: Yuri Volchkov <yuri.volchkov@xxxxxxxxx>

I have no clue how the algorithm works, but I choose to trust you here :)

Me neither ;-), we have to trust the source. It is anyway just the first and initial implementation. Others may come ;-)


Sharan Santhanam <sharan.santhanam@xxxxxxxxx> writes:

Implementation a psuedo random number generator.

Signed-off-by: Simon Kuenzer <simon.kuenzer@xxxxxxxxx>
Signed-off-by: Sharan Santhanam <sharan.santhanam@xxxxxxxxx>
---
  lib/Config.uk                    |   1 +
  lib/Makefile.uk                  |   1 +
  lib/ukswrand/Config.uk           |  20 ++++++++
  lib/ukswrand/Makefile.uk         |   6 +++
  lib/ukswrand/export.syms         |   2 +
  lib/ukswrand/include/uk/swrand.h |  70 ++++++++++++++++++++++++++
  lib/ukswrand/mwc.c               | 103 +++++++++++++++++++++++++++++++++++++++
  7 files changed, 203 insertions(+)
  create mode 100644 lib/ukswrand/Config.uk
  create mode 100644 lib/ukswrand/Makefile.uk
  create mode 100644 lib/ukswrand/export.syms
  create mode 100644 lib/ukswrand/include/uk/swrand.h
  create mode 100644 lib/ukswrand/mwc.c

diff --git a/lib/Config.uk b/lib/Config.uk
index 5bf5ebc..0a78a02 100644
--- a/lib/Config.uk
+++ b/lib/Config.uk
@@ -33,3 +33,4 @@ source "lib/ukallocbbuddy/Config.uk"
  source "lib/uksched/Config.uk"
  source "lib/ukschedcoop/Config.uk"
  source "lib/fdt/Config.uk"
+source "lib/ukswrand/Config.uk"
diff --git a/lib/Makefile.uk b/lib/Makefile.uk
index 1d7cb57..d549152 100644
--- a/lib/Makefile.uk
+++ b/lib/Makefile.uk
@@ -5,6 +5,7 @@
  
################################################################################
$(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/ukboot))
+$(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/ukswrand))
  $(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/ukdebug))
  $(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/ukargparse))
  $(eval $(call _import_lib,$(CONFIG_UK_BASE)/lib/uktimeconv))
diff --git a/lib/ukswrand/Config.uk b/lib/ukswrand/Config.uk
new file mode 100644
index 0000000..44f6ee5
--- /dev/null
+++ b/lib/ukswrand/Config.uk
@@ -0,0 +1,20 @@
+menuconfig LIBUKSWRAND
+       bool "ukswrand: Software random number generator"
+       select LIBUKDEBUG
+       default n
+
+if LIBUKSWRAND
+choice
+       prompt "Algorithm"
+       default LIBUKSWRAND_MWC
+
+config LIBUKSWRAND_MWC
+       bool "Multiply-with-carry"
+       help
+               Use multiply-with-carry algorithm
+endchoice
+
+config LIBUKSWRAND_INITIALSEED
+       int "Initial random seed"
+       default 23
+endif
diff --git a/lib/ukswrand/Makefile.uk b/lib/ukswrand/Makefile.uk
new file mode 100644
index 0000000..8d4482c
--- /dev/null
+++ b/lib/ukswrand/Makefile.uk
@@ -0,0 +1,6 @@
+$(eval $(call addlib_s,libukswrand,$(CONFIG_LIBUKSWRAND)))
+
+CINCLUDES-$(CONFIG_LIBUKSWRAND)        += -I$(LIBUKSWRAND_BASE)/include
+CXXINCLUDES-$(CONFIG_LIBUKSWRAND) += -I$(LIBUKSWRAND_BASE)/include
+
+LIBUKSWRAND_SRCS-$(CONFIG_LIBUKSWRAND_MWC) += $(LIBUKSWRAND_BASE)/mwc.c
diff --git a/lib/ukswrand/export.syms b/lib/ukswrand/export.syms
new file mode 100644
index 0000000..92f2be3
--- /dev/null
+++ b/lib/ukswrand/export.syms
@@ -0,0 +1,2 @@
+uk_swrand_init_r
+uk_swrand_randr_r
diff --git a/lib/ukswrand/include/uk/swrand.h b/lib/ukswrand/include/uk/swrand.h
new file mode 100644
index 0000000..e2e43f9
--- /dev/null
+++ b/lib/ukswrand/include/uk/swrand.h
@@ -0,0 +1,70 @@
+/* SPDX-License-Identifier: BSD-3-Clause */
+/*
+ * Authors: Simon Kuenzer <simon.kuenzer@xxxxxxxxx>
+ *
+ * Copyright (c) 2018, NEC Europe Ltd., NEC Corporation. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the copyright holder nor the names of its
+ *    contributors may be used to endorse or promote products derived from
+ *    this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * THIS HEADER MAY NOT BE EXTRACTED OR MODIFIED IN ANY WAY.
+ */
+
+#ifndef __UK_SWRAND__
+#define __UK_SWRAND__
+
+#include <uk/arch/types.h>
+#include <uk/plat/lcpu.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct uk_swrand;
+extern struct uk_swrand uk_swrand_def;
+
+void uk_swrand_init_r(struct uk_swrand *r, __u32 seed);
+__u32 uk_swrand_randr_r(struct uk_swrand *r);
+
+/* Uses the pre-initialized default generator  */
+/* TODO: Add assertion when we can test if we are in interrupt context */
+/* TODO: Revisit with multi-CPU support */
+static inline __u32 uk_swrand_randr(void)
+{
+       unsigned long iflags;
+       __u32 ret;
+
+       iflags = ukplat_lcpu_save_irqf();
+       ret = uk_swrand_randr_r(&uk_swrand_def);
+       ukplat_lcpu_restore_irqf(iflags);
+
+       return ret;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __UK_SWRAND__ */
diff --git a/lib/ukswrand/mwc.c b/lib/ukswrand/mwc.c
new file mode 100644
index 0000000..60a5bf1
--- /dev/null
+++ b/lib/ukswrand/mwc.c
@@ -0,0 +1,103 @@
+/* SPDX-License-Identifier: BSD-3-Clause */
+/*
+ * Authors: Florian Schmidt <florian.schmidt@xxxxxxxxx>
+ *          Simon Kuenzer <simon.kuenzer@xxxxxxxxx>
+ *
+ * Copyright (c) 2018, NEC Europe Ltd., NEC Corporation. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the copyright holder nor the names of its
+ *    contributors may be used to endorse or promote products derived from
+ *    this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * THIS HEADER MAY NOT BE EXTRACTED OR MODIFIED IN ANY WAY.
+ */
+
+#include <uk/swrand.h>
+#include <uk/print.h>
+#include <uk/assert.h>
+#include <uk/plat/ctors.h>
+
+/* 
https://stackoverflow.com/questions/9492581/c-random-number-generation-pure-c-code-no-libraries-or-functions
 */
+#define PHI 0x9e3779b9
+#define UK_SWRAND_CTOR_PRIO    (200U)
+
+struct uk_swrand {
+       __u32 Q[4096];
+       __u32 c;
+       __u32 i;
+};
+
+struct uk_swrand uk_swrand_def;
+
+/*
+ * Declare the constructor function to initialize the swrand
+ */
+static void _uk_swrand_ctor(void) __constructor_prio(UK_SWRAND_CTOR_PRIO);
+
+void uk_swrand_init_r(struct uk_swrand *r, __u32 seed)
+{
+       __u32 i;
+
+       UK_ASSERT(r);
+
+       r->Q[0] = seed;
+       r->Q[1] = seed + PHI;
+       r->Q[2] = seed + PHI + PHI;
+       for (i = 3; i < 4096; i++)
+               r->Q[i] = r->Q[i - 3] ^ r->Q[i - 2] ^ PHI ^ i;
+
+       r->c = 362436;
+       r->i = 4095;
+}
+
+__u32 uk_swrand_randr_r(struct uk_swrand *r)
+{
+       __u64 t, a = 18782LL;
+       __u32 x, y = 0xfffffffe;
+       __u32 i, c;
+
+       UK_ASSERT(r);
+
+       i = r->i;
+       c = r->c;
+
+       i = (i + 1) & 4095;
+       t = a * r->Q[i] + c;
+       c = (t >> 32);
+       x = t + c;
+       if (x < c) {
+               x++;
+               c++;
+       }
+
+       r->i = i;
+       r->c = c;
+       return (r->Q[i] = y - x);
+}
+
+static void _uk_swrand_ctor(void)
+{
+       uk_printd(DLVL_INFO, "Initialize random number generator...\n");
+       uk_swrand_init_r(&uk_swrand_def, CONFIG_LIBUKSWRAND_INITIALSEED);
+}
--
2.7.4


_______________________________________________
Minios-devel mailing list
Minios-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/minios-devel


_______________________________________________
Minios-devel mailing list
Minios-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/minios-devel

 


Rackspace

Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.