From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-1.0 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id E5C33C43381 for ; Tue, 26 Mar 2019 14:58:48 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id B3EA92075C for ; Tue, 26 Mar 2019 14:58:47 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=networkplumber-org.20150623.gappssmtp.com header.i=@networkplumber-org.20150623.gappssmtp.com header.b="FmkbntZd" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731715AbfCZO6q (ORCPT ); Tue, 26 Mar 2019 10:58:46 -0400 Received: from mail-pl1-f178.google.com ([209.85.214.178]:37402 "EHLO mail-pl1-f178.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726175AbfCZO6q (ORCPT ); Tue, 26 Mar 2019 10:58:46 -0400 Received: by mail-pl1-f178.google.com with SMTP id q6so1754073pll.4 for ; Tue, 26 Mar 2019 07:58:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=networkplumber-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=jDya257BUMQbIqjlv+gnKtnJLvzBWJzFfYurtDuJ/dU=; b=FmkbntZdlNKTW4E4okYxUUhU338act0rhCqb2H5d861NWlpFoedxtuIA85KRuWjkuC ymbRuA/hydW/drGFYm1k5AVRGfr46TKrV6NPt/3XfkIxJHiD1yZWjrR4i4Wt+Vz+UFDY QMuvmHFVriy8S3TtAHCNGLYCkWlZGVMKGObvjivkJK2AHA0bLmJxrvsDZPt78spXS2Iy LN1Z2cjXG2KnHvPtnacMiCAD6FDOQ5uiL0kmr4v2oT/5dd6+QIgJP2vPKsXDEwLmwI8s 4PTCypwzWunGBTHUdFLxgzglDt5Y8XANY0BnuQ4j5FBqYYH7JVFQ/7WTdUrPnIfS5QLi WtSg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=jDya257BUMQbIqjlv+gnKtnJLvzBWJzFfYurtDuJ/dU=; b=nUcSjOUJqGjsCSByYHmRoDl8b29zVEaWAmLe+Qb8tlr/TZgS5ys8Ox2hcic6e4TOPw mil1pRYY9si44GZ3oPqOtpHtCDQE+Hgz9gG4lC/jDSmgjnboAtPJvFUpQVW9vQr/pI7M qnTDAYkDQCptUOB/HoigA8eOmhw45M6whcTbUChiN4IuCAgik7JUXYyoMlH8v9+KBYB9 /YCTTtkWgUd8QIHzrQ2p2wkra8h6IttvIb+wwbRJuLw99x2IdmnOJ0AKhIWRZCUWFQQC QsLshkK1Iy5QYe3191AcKXym8NndkBaPiz5URPvr2DWCt6sM+LtFP5HrMvIuc/h3tjSW ldGg== X-Gm-Message-State: APjAAAVcvPL4e9rRhUQgwZNx3FhKlVsEHjc8iNCm9W3SGM0DAZOPP3Jv QaoRcCA/vtOtSyaZbiPtLk8kMg== X-Google-Smtp-Source: APXvYqxO0iPvyVC/thKFKm2IurhVdrOwxEaIHqVnt+mLzPSRm0DGoDHEMhzVajdOK25owJliQNS9aQ== X-Received: by 2002:a17:902:b60c:: with SMTP id b12mr30940079pls.261.1553612325430; Tue, 26 Mar 2019 07:58:45 -0700 (PDT) Received: from shemminger-XPS-13-9360 (204-195-22-127.wavecable.com. [204.195.22.127]) by smtp.gmail.com with ESMTPSA id t3sm22176102pgv.39.2019.03.26.07.58.44 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Tue, 26 Mar 2019 07:58:45 -0700 (PDT) Date: Tue, 26 Mar 2019 07:58:39 -0700 From: Stephen Hemminger To: George Spelvin Cc: , , Borkmann@sdf.org, Daniel@sdf.org, Frederic@sdf.org, Hannes@sdf.org, Sowa@sdf.org, George@sdf.org, netdev@vger.kernel.org, Spelvin@sdf.org Subject: Re: Revising prandom_32 generator Message-ID: <20190326075839.5a94442b@shemminger-XPS-13-9360> In-Reply-To: <201903261110.x2QBAFmp001613@sdf.org> References: <201903261110.x2QBAFmp001613@sdf.org> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org On Tue, 26 Mar 2019 11:10:15 GMT George Spelvin wrote: > I started on a project to correct all of the instances of > "prandom_u32() % FOO" in the kernel (there are lots) > to "prandom_u32_max(FOO)". > > This has snowballed into an ongoing audit of random number use in the > kernel, including uses of get_random_bytes() when get_random_u32 or > prandom_u32() would suffice. > > But one of the more potentially-controversial changes in the series, > which might benefit from more discussion time, is a change of the > actual prandom_u32() generator itself. > > The current lfsr113 generator isn't bad, but like all LFSRs, it fails > linear complexity tests in suites like testU01 and PractRand. > > And there are generators with the same 128-bit state which produce > better output in about half the time. So I figured as long as I was > neck-deep in the code, I might as well tweak that, too. > > Thw ones that seem interesting to me are: > - Chris Doty-Humphrey's sfc32. This is a 96-bit chaotic generator > (meaning period *probably* long but not well defined) fed with > a 32-bit counter to ensure a minimum period. It's extremely > fast, and the author is also the author of PractRand, so it's > well-tested. > - Vigna and Bacman's xoshiro128**. This is a 128-bit LFSR with some > output postprocessing. > - (on 64-bit machines) xoroshiro128**, by the same authors. > This is only efficient on 64-bit machines, so it would need > a have a 32-bit backup. > - Bob Jenkins' jsf (originally "flea"). 128 bits, good mixing, > fully chaotic. I prefer the safety of a guaranteed minimum > period, but this is well thought of. > - A lag-3 mutiply-with-carry generator. 2^32 - 1736 is the largest > "safe prime" mutiplier. > > I'm currently planning on using the first. It also has the advantage > for lockless reseeding that there are no bad states to avoid. > > Some discussion of most of these at > http://www.pcg-random.org/posts/some-prng-implementations.html > > Here are some timing numbers. Clock cycles per 1e7 iterations, > sp 8-19 cycles per iteration. > > Core 2: > lcg32: cycles 89018580 > lcg64: cycles 130782048 > mwc: cycles 90385992 > prandom_u32: cycles 168780348 > xoshiro128ss: cycles 90331056 > xoroshiro128ss: cycles 106012008 > sfc32: cycles 90318276 > jsf32: cycles 90364464 > jsf32a: cycles 100382724 > gjrand: cycles 131713680 > > Opteron: > lcg32: cycles 103434699 > lcg64: cycles 80064205 > mwc: cycles 110313786 > prandom_u32: cycles 190311062 > xoshiro128ss: cycles 110115475 > xoroshiro128ss: cycles 100114345 > sfc32: cycles 100163397 > jsf32: cycles 100104957 > jsf32a: cycles 110133030 > gjrand: cycles 110122007 > > (The LCGs are not 128-bit state; they're just there as a speed baseine.) > > As you can see, the current lfsr113-based prandom_u32 takes almost > twice the time of the aternatives. > > My quick & dirty test code is appended for anyone who wants to play. > A little backstory. I started the prandom_32 stuff long ago when I wanted a better (longer period) PRNG for use in netem. Took the existing code from older version of GNU scientific library (pre GPLv3). If there is something faster with better properties go for it. But the whole point of prandom_32 is that it doesn't have to be crypto quality.