On Mon, Mar 30, 2020 at 02:28:08PM +0100, Mark Rutland wrote: > Also, if you do send a series, *please* add a cover-letter explaining > what the overall purpose of the series is, and have all patches chained > in-reply-to that rather than patch 1. Otherwise reviewers have to > reverse-engineer the intent of the author. > > You can generate the cover letter with: > > $ git format-patch --cover $FROM..$TO > > ... and IIRC git send-email does the right thing by default if you hand > it all of the patches at once. Er, I *did* send a cover letter. Cc:ed to the union of everyone Cc:ed on any of the individual patches. It's appended. (I left in the full Cc: list so you can see you're on it.) My problem is I don't have git on my e-mail machine, so I fed them to sendmail manually, and that does some strange things. >From 0ca5529c065d9ec469c90ae56955386c91d0bced Mon Sep 17 00:00:00 2001 From: George Spelvin <lkml@xxxxxxx> Date: Thu, 26 Mar 2020 08:21:04 -0400 Subject: [RFC PATCH v1 00/52] Audit kernel random number use MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit To: linux-kernel@xxxxxxxxxxxxxxx, lkml@xxxxxxx Cc: "H. Peter Anvin" <hpa@xxxxxxxxx>, "Darrick J. Wong" <darrick.wong@xxxxxxxxxx>, "David S. Miller" <davem@xxxxxxxxxxxxx>, "J. Bruce Fields" <bfields@xxxxxxxxxxxx>, "Theodore Ts'o" <tytso@xxxxxxx>, Adrian Hunter <adrian.hunter@xxxxxxxxx>, Akinobu Mita <akinobu.mita@xxxxxxxxx>, Alexei Starovoitov <ast@xxxxxxxxxx>, Alexey Kuznetsov <kuznet@xxxxxxxxxxxxx>, Andreas Dilger <adilger.kernel@xxxxxxxxx>, Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>, Andrii Nakryiko <andriin@xxxxxx>, Andy Lutomirski <luto@xxxxxxxxxx>, Andy Shevchenko <andriy.shevchenko@xxxxxxxxxxxxxxx>, Anna Schumaker <anna.schumaker@xxxxxxxxxx>, Anton Blanchard <anton@xxxxxxxxx>, Antonio Quartulli <a@xxxxxxxxxxx>, Ard Biesheuvel <ard.biesheuvel@xxxxxxxxxx>, Arend van Spriel <arend.vanspriel@xxxxxxxxxxxx>, Artem Bityutskiy <dedekind1@xxxxxxxxx>, Aruna-Hewapathirane <aruna.hewapathirane@xxxxxxxxx>, Bart Van Assche <bvanassche@xxxxxxx>, Benjamin Herrenschmidt <benh@xxxxxxxxxxxxxxxxxxx>, Benjamin Tissoires <benjamin.tissoires@xxxxxxxxxx>, Bernard Metzler <bmt@xxxxxxxxxxxxxx>, Borislav Petkov <bp@xxxxxxxxx>, Brian Norris <computersforpeace@xxxxxxxxx>, Catalin Marinas <catalin.marinas@xxxxxxx>, Chi-Hsien Lin <chi-hsien.lin@xxxxxxxxxxx>, Chris Leech <cleech@xxxxxxxxxx>, Chris Wilson <chris@xxxxxxxxxxxxxxxxxx>, Chris Zankel <chris@xxxxxxxxxx>, Christian Borntraeger <borntraeger@xxxxxxxxxx>, Christian Lamparter <chunkeey@xxxxxxxxx>, Chuck Lever <chuck.lever@xxxxxxxxxx>, Cong Wang <xiyou.wangcong@xxxxxxxxx>, Dan Williams <dan.j.williams@xxxxxxxxx>, Daniel Borkmann <daniel@xxxxxxxxxxxxx>, Dave Hansen <dave.hansen@xxxxxxxxxxxxxxx>, David Woodhouse <dwmw2@xxxxxxxxxxxxx>, Davidlohr Bueso <dave@xxxxxxxxxxxx>, Dennis Dalessandro <dennis.dalessandro@xxxxxxxxx>, Dmitry Safonov <0x7f454c46@xxxxxxxxx>, Doug Ledford <dledford@xxxxxxxxxx>, Emmanuel Grumbach <emmanuel.grumbach@xxxxxxxxx>, Eric Biggers <ebiggers@xxxxxxxxxx>, Eric Dumazet <eric.dumazet@xxxxxxxxx>, Faisal Latif <faisal.latif@xxxxxxxxx>, Ferdinand Blomqvist <ferdinand.blomqvist@xxxxxxxxx>, Franky Lin <franky.lin@xxxxxxxxxxxx>, Hannes Frederic Sowa <hannes@xxxxxxxxxxxxxxxxxxx>, Hannes Reinecke <hare@xxxxxxx>, Hans de Goede <hdegoede@xxxxxxxxxx>, Hante Meuleman <hante.meuleman@xxxxxxxxxxxx>, Heiko Carstens <heiko.carstens@xxxxxxxxxx>, Herbert Xu <herbert@xxxxxxxxxxxxxxxxxxx>, Hideaki YOSHIFUJI <yoshfuji@xxxxxxxxxxxxxx>, Hsin-Yi Wang <hsinyi@xxxxxxxxxxxx>, Ilya Dryomov <idryomov@xxxxxxxxx>, Ingo Molnar <mingo@xxxxxxxxxx>, Intel Linux Wireless <linuxwifi@xxxxxxxxx>, Jamal Hadi Salim <jhs@xxxxxxxxxxxx>, James Hogan <jhogan@xxxxxxxxxx>, Jan Kara <jack@xxxxxxxx>, Jani Nikula <jani.nikula@xxxxxxxxxxxxxxx>, Jaroslav Kysela <perex@xxxxxxxx>, Jason A. Donenfeld <Jason@xxxxxxxxx>, Jason Gunthorpe <jgg@xxxxxxxx>, Jeff Layton <jlayton@xxxxxxxxxx>, Jiri Kosina <jkosina@xxxxxxx>, Jiri Pirko <jiri@xxxxxxxxxxx>, Joel Becker <jlbec@xxxxxxxxxxxx>, Johan Hovold <johan@xxxxxxxxxx>, Johannes Berg <johannes.berg@xxxxxxxxx>, Johannes Berg <johannes@xxxxxxxxxxxxxxxx>, Jon Maloy <jon.maloy@xxxxxxxxxxxx>, Joonas Lahtinen <joonas.lahtinen@xxxxxxxxxxxxxxx>, Joseph Qi <joseph.qi@xxxxxxxxxxxxxxxxx>, Ka-Cheong Poon <ka-cheong.poon@xxxxxxxxxx>, Kalle Valo <kvalo@xxxxxxxxxxxxxx>, Karsten Keil <isdn@xxxxxxxxxxxxxx>, Kees Cook <keescook@xxxxxxxxxxxx>, Lars Ellenberg <lars.ellenberg@xxxxxxxxxx>, Lee Duncan <lduncan@xxxxxxxx>, Luca Coelho <luciano.coelho@xxxxxxxxx>, Maciej Zenczykowski <maze@xxxxxxxxxx>, Marcelo Ricardo Leitner <marcelo.leitner@xxxxxxxxx>, Marek Lindner <mareklindner@xxxxxxxxxxxxx>, Marek Vasut <marek.vasut@xxxxxxxxx>, Mark Fasheh <mark@xxxxxxxxxx>, Martin Hundeboll <martin@xxxxxxxxxxxxx>, Martin KaFai Lau <kafai@xxxxxx>, Max Filippov <jcmvbkbc@xxxxxxxxx>, Mel Gorman <mgorman@xxxxxxx>, Michael Ellerman <mpe@xxxxxxxxxxxxxx>, Michal Hocko <mhocko@xxxxxxxx>, Mike Marciniszyn <mike.marciniszyn@xxxxxxxxx>, Miquel Raynal <miquel.raynal@xxxxxxxxxxx>, Neil Horman <nhorman@xxxxxxxxxxxxx>, Nicholas Bellinger <nab@xxxxxxxxxxxxxxx>, Paul Burton <paulburton@xxxxxxxxxx>, Paul Mackerras <paulus@xxxxxxxxx>, Peter Zijlstra <peterz@xxxxxxxxxxxxx>, Philipp Reisner <philipp.reisner@xxxxxxxxxx>, Potnuri Bharat Teja <bharat@xxxxxxxxxxx>, QLogic-Storage-Upstream@xxxxxxxxxx, Qian Cai <cai@xxxxxx>, Ralf Baechle <ralf@xxxxxxxxxxxxxx>, Rich Felker <dalias@xxxxxxxx>, Richard Weinberger <richard@xxxxxx>, Rodrigo Vivi <rodrigo.vivi@xxxxxxxxx>, Roman Gushchin <guro@xxxxxx>, Russell King <linux@xxxxxxxxxxxxxxx>, Sage Weil <sage@xxxxxxxxxx>, Samuel Ortiz <sameo@xxxxxxxxxxxxxxx>, Santosh Shilimkar <santosh.shilimkar@xxxxxxxxxx>, Sean Rees <sean@xxxxxxxxxx>, Sebastian Andrzej Siewior <bigeasy@xxxxxxxxxxxxx>, Shiraz Saleem <shiraz.saleem@xxxxxxxxx>, Simon Wood <simon@xxxxxxxxxxxxx>, Simon Wunderlich <sw@xxxxxxxxxxxxxxxxxx>, Song Liu <songliubraving@xxxxxx>, Steffen Klassert <steffen.klassert@xxxxxxxxxxx>, Stephen Hemminger <stephen@xxxxxxxxxxxxxxxxxx>, Sven Eckelmann <sven@xxxxxxxxxxxxx>, Takashi Iwai <tiwai@xxxxxxxx>, Thomas Garnier <thgarnie@xxxxxxxxxxxx>, Thomas Garnier <thgarnie@xxxxxxxxxx>, Thomas Gleixner <tglx@xxxxxxxxxxxxx>, Thomas Hellstrom <thellstrom@xxxxxxxxxx>, Trond Myklebust <trond.myklebust@xxxxxxxxxxxxxxx>, Uladzislau Rezki (Sony) <urezki@xxxxxxxxx>, Ulf Hansson <ulf.hansson@xxxxxxxxxx>, Vasily Gorbik <gor@xxxxxxxxxxxxx>, Vignesh Raghavendra <vigneshr@xxxxxx>, Vitaly Kuznetsov <vkuznets@xxxxxxxxxx>, Vlad Yasevich <vyasevich@xxxxxxxxx>, Will Deacon <will@xxxxxxxxxx>, Wright Feng <wright.feng@xxxxxxxxxxx>, Ying Xue <ying.xue@xxxxxxxxxxxxx>, Yonghong Song <yhs@xxxxxx>, Yoshinori Sato <ysato@xxxxxxxxxxxxxxxxxxxx>, Yu Zhao <yuzhao@xxxxxxxxxx>, alsa-devel@xxxxxxxxxxxxxxxx, bpf@xxxxxxxxxxxxxxx, brcm80211-dev-list.pdl@xxxxxxxxxxxx, brcm80211-dev-list@xxxxxxxxxxx, ceph-devel@xxxxxxxxxxxxxxx, intel-gfx@xxxxxxxxxxxxxxxxxxxxx, isdn4linux@xxxxxxxxxxxxxxxxxxxxxx, linux-arm-kernel@xxxxxxxxxxxxxxxxxxx, linux-crypto@xxxxxxxxxxxxxxx, linux-ext4@xxxxxxxxxxxxxxx, linux-mips@xxxxxxxxxxxxxxx, linux-mm@xxxxxxxxx, linux-mmc@xxxxxxxxxxxxxxx, linux-mtd@xxxxxxxxxxxxxxxxxxx, linux-nfc@xxxxxxxxxxxx, linux-nfs@xxxxxxxxxxxxxxx, linux-rdma@xxxxxxxxxxxxxxx, linux-s390@xxxxxxxxxxxxxxx, linux-scsi@xxxxxxxxxxxxxxx, linux-sctp@xxxxxxxxxxxxxxx, linux-sh@xxxxxxxxxxxxxxx, linux-wireless@xxxxxxxxxxxxxxx, linux-xfs@xxxxxxxxxxxxxxx, linux-xtensa@xxxxxxxxxxxxxxxx, linuxppc-dev@xxxxxxxxxxxxxxxx, netdev@xxxxxxxxxxxxxxx, netem@xxxxxxxxxxxxxxxxxxxxxxxxxx, ocfs2-devel@xxxxxxxxxxxxxx, rds-devel@xxxxxxxxxxxxxx, tipc-discussion@xxxxxxxxxxxxxxxxxxxxx, x86@xxxxxxxxxx Sorry for the long Cc list, but this is a treewide cleanup and I wanted to send this cover letter to everyone. Individual patches are Cc: the relevant maintainers, and the whole series can be found on linux-kernel@vger. The original itch I wanted to scratch was fixing the numerous instances of "get_random_u32() % range" and "prandom_u32() % range" in the kernel. % is fast to type but slow to execute: even in the optimized special case that the range is a compile-time constant, the modulo requires two multiplies to evaluate. prandom_u32_max() works better; it used reciprocal_scale(), which ends up doing (u64)prandom_u32() * range >> 32". This is not only faster and less code, the random numbers are more uniform. When the range is not a power of 2, some outputs are generated more often than others. With the modulo technique, those are all the outputs less than 0x100000000 % range. When multiplying, the overrepresented outputs are at least spread uniformly across the possible outputs. The multiplicative technique can also be easily extended to generate perfectly uniform random numbers (by detecting an overrepresented case and looping if it happens) if desired. But as I started in on the project, I kept finding more things that needed fixing. This patch series is what I have ready at the moment. I could use feedback on individual patches, but also the series as a whole. How should it be broken up? How should it be submitted? Perhaps, with this series as motivation, merge the random.[ch] changes, and then do the rest piecemeal? The series (currently based on v5.5.10) consists of: 01..07: These are various bugs I came across while looking for code to replace. They are independent of the rest of the series, but related. 08: (EXT4) This is a bit of code I'm not sure about. Sometimes a random number is used, and sometimes a hash is used as input to the range reduction. Does the modulo have to be preserved for backward compatibility? 09: If the range is a compile-time constant power of 2, then gcc optimizes the modulo better than the multiply in prandom_u32_max(). This patch fixes that, so that you don't have to worry about the numerical value of the range; prandom_u32_max() is always as good or better. 10: This is a very optional patch, for disucssion. When the range is a compile-time constant, making the output of prandom_u32_max() perfectly uniform is quite cheap. This adds the extra test and retry loop to that common special case. Worth bothering? 11: This is the big one (which probably needs to be broken up by subsystem), doing a treewide replacement of prandom_u32() % range, when the range is not obviously a power of 2. 12: The same, for prandom_u32_state() 13..19: These are patches that were pulled out of the previous two because they're involve some more complex code changes. 20..23: Changes to the prandom_u32() generator itself. Including switching to a stronger & faster PRNG. 24..35: Places where crypto-strength get_random_* was used, but only pseudorandom numbers are justified. Examples are: - self-test code - Seeding other PRNGs - random backoffs and timeouts 36..38: Improvements to the batched entropy pool in random.c. 39: (ARM64) Avoid the need for a temporary buffer (and subsequent wiping) when transferring random seed material across kexec. 40..44: Replace get_random_bytes() with get_random_{u32,u64,long}, where the slightly weaker security guarantees of the latter suffice. 45: Add a get_random_max() function, using batched crypto-quality entropy. This is more complex than prandom_u32_max() because it has to support 64-bit results and is perfectly uniform in all cases. 46..49: Use get_random_max in various applications 50: Is the first part of the next phase. This adds a function to fill a byte buffer from the batched entropy buffer, a drop-in replacement for get_random_bytes(). I'm particularly seeking comment on what this function, with its different security guarantees, should be called. One option I'm considering is to name it get_random_bytes, and move the (relatively few) call sites that really need unbacktrackable random numbers to another name like get_secret_bytes(). George Spelvin (50): IB/qib: Delete struct qib_ivdev.qp_rnd lib/fault-inject.c: Fix off-by-one error in probability fault-inject: Shrink struct fault_attr batman-adv: fix batadv_nc_random_weight_tq net/rds/bind.c: Use prandom_u32_max() ubi/debug: Optimize computation of odds mm/slab: Use simpler Fisher-Yates shuffle fs/ext4/ialloc.c: Replace % with reciprocal_scale() TO BE VERIFIED <linux/random.h> prandom_u32_max() for power-of-2 ranges <linux/random.h> Make prandom_u32_max() exact for constant ranges Treewide: Extirpate "prandom_u32() % range" Treewide: Extirpate prandom_u32_state(rnd) % range Avoid some useless msecs/jiffies conversions crypto/testmgr.c: use prandom_u32_max() & prandom_bytes() drivers/block/drbd/drbd_main: fix _drbd_fault_random() include/net/red.h: Simplify red_random() TO BE VERIFIED net/802/{garp,mrp}.c: Use prandom_u32_max instead of manual equivalent net/ipv6/addrconf.c: Use prandom_u32_max for rfc3315 backoff time computation net/sched/sch_netem: Simplify get_crandom lib/random32: Move prandom_warmup() inside prandom_seed_early() lib/random32.c: Change to SFC32 PRNG lib/random32: Use random_ready_callback for seeding. prandom_seed_state(): Change to 32-bit seed type. crypto4xx_core: Use more appropriate seed for PRNG HID: hid-lg: We only need pseudorandom bytes for the address drivers/nfc/nfcsim: use prandom_32() for time delay drivers/s390/scsi/zcsp_fc.c: Use prandom_u32_max() for backoff drivers/target/iscsi: Replace O(n^2) randomization fs/ocfs2/journal: Use prandom_u32() and not /dev/random for timeout kernel/locking/test-ww_mutex.c: Use cheaper prandom_u32_max() lib/nodemask.c: Use cheaper prandom_u32_max() in node_random() lib/test*.c: Use prandom_u32_max() lib/test_vmalloc.c: Use pseudorandom numbers mm/slub.c: Use cheaper prandom source in shuffle_freelist USB: serial: iuu_phoenix: Use pseudorandom for xmas mode random: Merge batched entropy buffers random: Simplify locking of batched entropy random: use chacha_permute() directly arm: kexec_file: Avoid temp buffer for RNG seed arch/*/include/asm/stackprotector.h: Use get_random_canary() consistently drivers/block/drbd/drbd_nl.c: Use get_random_u64() drivers/ininiband: Use get_random_u32() drivers/isdn: Use get_random_u32() arm64: ptr auth: Use get_random_u64 instead of _bytes random: add get_random_max() function mm/shuffle.c: use get_random_max() kernel/bpf/core.c: Use get_random_max32() arch/arm/kernel/process.c: Use get_random_max32() for sigpage_addr() arch/x86/entry/vdso/vma.c: Use get_random_max32() for vdso_addr random: add get_random_nonce() arch/arm/include/asm/stackprotector.h | 9 +- arch/arm/kernel/process.c | 2 +- arch/arm64/include/asm/pointer_auth.h | 20 +- arch/arm64/include/asm/stackprotector.h | 8 +- arch/arm64/kernel/machine_kexec_file.c | 8 +- arch/arm64/kernel/pointer_auth.c | 62 +- arch/mips/include/asm/stackprotector.h | 7 +- arch/powerpc/include/asm/stackprotector.h | 6 +- arch/sh/include/asm/stackprotector.h | 8 +- arch/x86/entry/vdso/vma.c | 2 +- arch/x86/include/asm/stackprotector.h | 4 +- arch/x86/mm/pageattr-test.c | 4 +- arch/xtensa/include/asm/stackprotector.h | 7 +- crypto/testmgr.c | 21 +- drivers/block/drbd/drbd_main.c | 37 +- drivers/block/drbd/drbd_nl.c | 4 +- drivers/char/random.c | 581 +++++++++++++----- drivers/crypto/amcc/crypto4xx_core.c | 7 +- drivers/crypto/chelsio/chtls/chtls_io.c | 4 +- drivers/gpu/drm/i915/selftests/i915_gem_gtt.c | 2 +- drivers/gpu/drm/i915/selftests/scatterlist.c | 4 +- drivers/hid/hid-lg.c | 2 +- drivers/infiniband/core/cm.c | 2 +- drivers/infiniband/core/cma.c | 5 +- drivers/infiniband/core/sa_query.c | 2 +- drivers/infiniband/hw/cxgb4/id_table.c | 4 +- drivers/infiniband/hw/i40iw/i40iw_verbs.c | 2 +- drivers/infiniband/hw/qib/qib_verbs.c | 2 - drivers/infiniband/hw/qib/qib_verbs.h | 1 - drivers/infiniband/sw/siw/siw_mem.c | 9 +- drivers/infiniband/sw/siw/siw_verbs.c | 2 +- drivers/infiniband/ulp/srp/ib_srp.c | 3 +- drivers/isdn/mISDN/tei.c | 5 +- drivers/mmc/core/core.c | 4 +- drivers/mtd/nand/raw/nandsim.c | 4 +- drivers/mtd/tests/mtd_nandecctest.c | 10 +- drivers/mtd/tests/stresstest.c | 15 +- drivers/mtd/ubi/debug.c | 2 +- drivers/mtd/ubi/debug.h | 6 +- drivers/net/ethernet/broadcom/cnic.c | 3 +- .../broadcom/brcm80211/brcmfmac/p2p.c | 2 +- .../net/wireless/intel/iwlwifi/mvm/mac-ctxt.c | 2 +- drivers/nfc/nfcsim.c | 3 +- drivers/s390/scsi/zfcp_fc.c | 2 +- drivers/scsi/fcoe/fcoe_ctlr.c | 10 +- drivers/scsi/qedi/qedi_main.c | 2 +- .../target/iscsi/iscsi_target_seq_pdu_list.c | 72 +-- drivers/usb/serial/iuu_phoenix.c | 7 +- fs/ceph/inode.c | 2 +- fs/ceph/mdsmap.c | 2 +- fs/ext2/ialloc.c | 3 +- fs/ext4/ialloc.c | 5 +- fs/ext4/super.c | 8 +- fs/ocfs2/journal.c | 7 +- fs/ubifs/debug.c | 11 +- fs/ubifs/lpt_commit.c | 12 +- fs/xfs/xfs_error.c | 2 +- include/crypto/chacha.h | 1 + include/linux/fault-inject.h | 4 +- include/linux/random.h | 279 ++++++++- include/net/red.h | 22 +- kernel/bpf/core.c | 4 +- kernel/locking/test-ww_mutex.c | 23 +- lib/crypto/chacha.c | 2 +- lib/fault-inject.c | 12 +- lib/find_bit_benchmark.c | 4 +- lib/interval_tree_test.c | 9 +- lib/nodemask.c | 2 +- lib/random32.c | 558 +++++++++-------- lib/rbtree_test.c | 2 +- lib/reed_solomon/test_rslib.c | 4 +- lib/sbitmap.c | 7 +- lib/test-string_helpers.c | 2 +- lib/test_bpf.c | 2 +- lib/test_hexdump.c | 10 +- lib/test_list_sort.c | 2 +- lib/test_parman.c | 2 +- lib/test_vmalloc.c | 58 +- mm/shuffle.c | 2 +- mm/slab.c | 25 +- mm/slab_common.c | 15 +- mm/slub.c | 2 +- mm/swapfile.c | 2 +- net/802/garp.c | 2 +- net/802/mrp.c | 2 +- net/batman-adv/bat_iv_ogm.c | 4 +- net/batman-adv/bat_v_elp.c | 2 +- net/batman-adv/bat_v_ogm.c | 10 +- net/batman-adv/network-coding.c | 9 +- net/bluetooth/hci_request.c | 2 +- net/ceph/mon_client.c | 2 +- net/core/neighbour.c | 6 +- net/core/pktgen.c | 20 +- net/core/stream.c | 2 +- net/ipv4/igmp.c | 6 +- net/ipv4/inet_connection_sock.c | 2 +- net/ipv6/addrconf.c | 17 +- net/ipv6/mcast.c | 10 +- net/packet/af_packet.c | 2 +- net/rds/bind.c | 2 +- net/sched/act_gact.c | 2 +- net/sched/act_sample.c | 2 +- net/sched/sch_netem.c | 23 +- net/sctp/socket.c | 2 +- net/sunrpc/xprtsock.c | 2 +- net/tipc/socket.c | 5 +- net/wireless/scan.c | 2 +- net/xfrm/xfrm_state.c | 2 +- sound/core/pcm_lib.c | 2 +- sound/core/pcm_native.c | 2 +- 110 files changed, 1324 insertions(+), 917 deletions(-) -- 2.26.0