|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [Minios-devel] [UNIKRAFT PATCH 3/5] lib/ukswrand: Introduce libukswrand
Reviewed-by: Yuri Volchkov <yuri.volchkov@xxxxxxxxx>
I have no clue how the algorithm works, but I choose to trust you here :)
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
--
Yuri Volchkov
Software Specialist
NEC Europe Ltd
Kurfürsten-Anlage 36
D-69115 Heidelberg
_______________________________________________
Minios-devel mailing list
Minios-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/minios-devel
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |