From patchwork Thu Nov 18 18:46:45 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Alex_Benn=C3=A9e?= X-Patchwork-Id: 12693075 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 19C8EC433F5 for ; Thu, 18 Nov 2021 18:51:28 +0000 (UTC) Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id D44BC61AFD for ; Thu, 18 Nov 2021 18:51:27 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.1 mail.kernel.org D44BC61AFD Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=linaro.org Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-Id:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=idPmB/juqLiHLX6MldLaT2E6a+67Nuc90KkWN09GIdc=; b=AYRfTV/yxNlNoO K537K0UE72gHr31CYkzQ5fGWgyh/yYWAJWeVMUd5vOzcI3mKsIARWp7P+l6RETmmHHkHt7Va2clfL uI2AQXnz27W7TnCdD8fGsCr7Rv9G+XLrTNrdSGOh1ZtS64QfnppXE59xtzBEgPOm5LwaqmDXYHzUN Vamo1H4SF7D28vRRXcWsyzRKzDtrIfdTc/6toZ0c+K5NmoP1Ee9xnZTB3Mi5PRUM4qLdWh/hmjJ2a mwkKfxcSMof0EuC5z8OfFNT5XDjRwzbSPhFYQN6Y/BdafQtKLtgQR6zE52MuRZ498cUDusAuMkvuA EFxYgBcz/MsEnajoul3A==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1mnmTk-008e3k-BE; Thu, 18 Nov 2021 18:49:48 +0000 Received: from mail-wm1-x32f.google.com ([2a00:1450:4864:20::32f]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1mnmR7-008cwy-7X for linux-arm-kernel@lists.infradead.org; Thu, 18 Nov 2021 18:47:07 +0000 Received: by mail-wm1-x32f.google.com with SMTP id p3-20020a05600c1d8300b003334fab53afso8451161wms.3 for ; Thu, 18 Nov 2021 10:47:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=hk3bzlKoxpZyDrrCE6PtbaVaXFgnlPYcxwsdlufAHz0=; b=I43S0rspR+9J8s4VPXSwP0qyAG5XgbNXHbzEd835vMuI7wuTMavLxF7tWdRLqOMS0y e59iO9k++LXYhBppdh31y+jrY77McfWBpeFfblKi+SHAMwp3O9C6UfOFH2vWzw99n0W2 Fdw7EYaEqtfZtIObXsnYWMYOdEn3gM0oiW0glfAzGKRuEETBfs0Tx1h3d/14eoL0Ah5G FGAOyCY3DSA6KazwWqVGE8YkG9pPRxJ1OhHQDVURFTtMPz37nA1d3MZV7ZQOjebdFXu/ 2TNnrkru4w3C8CiMDUm+zUGlIZyl5WZpJOINtNhePY8GX7fsplROp928dF2Qr7yKuRlB IE/g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=hk3bzlKoxpZyDrrCE6PtbaVaXFgnlPYcxwsdlufAHz0=; b=Yaf/Un+Ye1yawPIrQwXp4U12J8iwa6jRSnkQ14auxpfF87wmBrfevaJ4hYGmRQkI42 Lu2QoyEc5gAbBXhpybaqWeGtAru9xBYkOvpPAjBBLIblJ/0JUzDosdoHTPKPxLHu/XKg 5cyyE31gABvfL4Kaluoxt66/F5YirrGjoZ1YESoeF9trrNuANF8PmiNeRjLasMKmYSF6 /xvv2EjiykM6U78gztL7N90jus90chxEgudAMkKuM3mEQ5xJYkRuq/tXXrSyZgDyszlB P6YmsR2ByHgc/3DP48CPoxoT3tAfEJ/7mp0woEk4hFzsreQOv55LU916gUV9PHBCEB6L A+NA== X-Gm-Message-State: AOAM530D89yYvuAlGAGXb6ziZFZDKk0rUBxnhHOQDOc83i1zUj8R0P0A 6geQZvjE9rF+H3zf3Mu2EWqufA== X-Google-Smtp-Source: ABdhPJwenmIb9vjZ9kptMGO/3EYwW5+5ywUMVFwd1C+3xnaj5wrhMgI/Yra/+F6z1kZFHXsAdH4uSw== X-Received: by 2002:a7b:c257:: with SMTP id b23mr12531384wmj.67.1637261223275; Thu, 18 Nov 2021 10:47:03 -0800 (PST) Received: from zen.linaroharston ([51.148.130.216]) by smtp.gmail.com with ESMTPSA id s8sm697055wra.9.2021.11.18.10.46.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 18 Nov 2021 10:46:55 -0800 (PST) Received: from zen.lan (localhost [127.0.0.1]) by zen.linaroharston (Postfix) with ESMTP id 64ADB1FF9C; Thu, 18 Nov 2021 18:46:50 +0000 (GMT) From: =?utf-8?q?Alex_Benn=C3=A9e?= To: kvm@vger.kernel.org Cc: idan.horowitz@gmail.com, qemu-arm@nongnu.org, linux-arm-kernel@lists.infradead.org, kvmarm@lists.cs.columbia.edu, christoffer.dall@arm.com, maz@kernel.org, =?utf-8?q?Alex_Benn=C3=A9e?= , "Timothy B . Terriberry" , Andrew Jones Subject: [kvm-unit-tests PATCH v8 05/10] lib: add isaac prng library from CCAN Date: Thu, 18 Nov 2021 18:46:45 +0000 Message-Id: <20211118184650.661575-6-alex.bennee@linaro.org> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20211118184650.661575-1-alex.bennee@linaro.org> References: <20211118184650.661575-1-alex.bennee@linaro.org> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20211118_104705_366645_49DF556D X-CRM114-Status: GOOD ( 25.08 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org It's often useful to introduce some sort of random variation when testing several racing CPU conditions. Instead of each test implementing some half-arsed PRNG bring in a a decent one which has good statistical randomness. Obviously it is deterministic for a given seed value which is likely the behaviour you want. I've pulled in the ISAAC library from CCAN: http://ccodearchive.net/info/isaac.html I shaved off the float related stuff which is less useful for unit testing and re-indented to fit the style. The original license was CC0 (Public Domain) which is compatible with the LGPL v2 of kvm-unit-tests. Signed-off-by: Alex Bennée CC: Timothy B. Terriberry Acked-by: Andrew Jones --- arm/Makefile.common | 1 + lib/prng.h | 82 ++++++++++++++++++++++ lib/prng.c | 162 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 245 insertions(+) create mode 100644 lib/prng.h create mode 100644 lib/prng.c diff --git a/arm/Makefile.common b/arm/Makefile.common index 38385e0..99bcf3f 100644 --- a/arm/Makefile.common +++ b/arm/Makefile.common @@ -44,6 +44,7 @@ cflatobjs += lib/pci-testdev.o cflatobjs += lib/virtio.o cflatobjs += lib/virtio-mmio.o cflatobjs += lib/chr-testdev.o +cflatobjs += lib/prng.o cflatobjs += lib/arm/io.o cflatobjs += lib/arm/setup.o cflatobjs += lib/arm/mmu.o diff --git a/lib/prng.h b/lib/prng.h new file mode 100644 index 0000000..bf5776d --- /dev/null +++ b/lib/prng.h @@ -0,0 +1,82 @@ +/* + * PRNG Header + */ +#ifndef __PRNG_H__ +#define __PRNG_H__ + +# include + + + +typedef struct isaac_ctx isaac_ctx; + + + +/*This value may be lowered to reduce memory usage on embedded platforms, at + the cost of reducing security and increasing bias. + Quoting Bob Jenkins: "The current best guess is that bias is detectable after + 2**37 values for [ISAAC_SZ_LOG]=3, 2**45 for 4, 2**53 for 5, 2**61 for 6, + 2**69 for 7, and 2**77 values for [ISAAC_SZ_LOG]=8."*/ +#define ISAAC_SZ_LOG (8) +#define ISAAC_SZ (1< +#include "prng.h" + +#define ISAAC_MASK (0xFFFFFFFFU) + +/* Extract ISAAC_SZ_LOG bits (starting at bit 2). */ +static inline uint32_t lower_bits(uint32_t x) +{ + return (x & ((ISAAC_SZ-1) << 2)) >> 2; +} + +/* Extract next ISAAC_SZ_LOG bits (starting at bit ISAAC_SZ_LOG+2). */ +static inline uint32_t upper_bits(uint32_t y) +{ + return (y >> (ISAAC_SZ_LOG+2)) & (ISAAC_SZ-1); +} + +static void isaac_update(isaac_ctx *_ctx){ + uint32_t *m; + uint32_t *r; + uint32_t a; + uint32_t b; + uint32_t x; + uint32_t y; + int i; + m=_ctx->m; + r=_ctx->r; + a=_ctx->a; + b=_ctx->b+(++_ctx->c); + for(i=0;i>6)+m[i+ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + x=m[++i]; + a=(a^a<<2)+m[i+ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + x=m[++i]; + a=(a^a>>16)+m[i+ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + } + for(i=ISAAC_SZ/2;i>6)+m[i-ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + x=m[++i]; + a=(a^a<<2)+m[i-ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + x=m[++i]; + a=(a^a>>16)+m[i-ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + } + _ctx->b=b; + _ctx->a=a; + _ctx->n=ISAAC_SZ; +} + +static void isaac_mix(uint32_t _x[8]){ + static const unsigned char SHIFT[8]={11,2,8,16,10,4,8,9}; + int i; + for(i=0;i<8;i++){ + _x[i]^=_x[(i+1)&7]<>SHIFT[i]; + _x[(i+3)&7]+=_x[i]; + _x[(i+1)&7]+=_x[(i+2)&7]; + } +} + + +void isaac_init(isaac_ctx *_ctx,const unsigned char *_seed,int _nseed){ + _ctx->a=_ctx->b=_ctx->c=0; + memset(_ctx->r,0,sizeof(_ctx->r)); + isaac_reseed(_ctx,_seed,_nseed); +} + +void isaac_reseed(isaac_ctx *_ctx,const unsigned char *_seed,int _nseed){ + uint32_t *m; + uint32_t *r; + uint32_t x[8]; + int i; + int j; + m=_ctx->m; + r=_ctx->r; + if(_nseed>ISAAC_SEED_SZ_MAX)_nseed=ISAAC_SEED_SZ_MAX; + for(i=0;i<_nseed>>2;i++){ + r[i]^=(uint32_t)_seed[i<<2|3]<<24|(uint32_t)_seed[i<<2|2]<<16| + (uint32_t)_seed[i<<2|1]<<8|_seed[i<<2]; + } + _nseed-=i<<2; + if(_nseed>0){ + uint32_t ri; + ri=_seed[i<<2]; + for(j=1;j<_nseed;j++)ri|=(uint32_t)_seed[i<<2|j]<<(j<<3); + r[i++]^=ri; + } + x[0]=x[1]=x[2]=x[3]=x[4]=x[5]=x[6]=x[7]=0x9E3779B9U; + for(i=0;i<4;i++)isaac_mix(x); + for(i=0;in)isaac_update(_ctx); + return _ctx->r[--_ctx->n]; +} + +uint32_t isaac_next_uint(isaac_ctx *_ctx,uint32_t _n){ + uint32_t r; + uint32_t v; + uint32_t d; + do{ + r=isaac_next_uint32(_ctx); + v=r%_n; + d=r-v; + } + while(((d+_n-1)&ISAAC_MASK)