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 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 16CCBC433F5 for ; Sat, 8 Oct 2022 03:50:48 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 39F636B0072; Fri, 7 Oct 2022 23:50:48 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 327DE6B0073; Fri, 7 Oct 2022 23:50:48 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 12CCD6B0074; Fri, 7 Oct 2022 23:50:48 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id EB8E06B0072 for ; Fri, 7 Oct 2022 23:50:47 -0400 (EDT) Received: from smtpin17.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id B55801A04BF for ; Sat, 8 Oct 2022 03:50:47 +0000 (UTC) X-FDA: 79996405734.17.2D83B5B Received: from mail-pf1-f173.google.com (mail-pf1-f173.google.com [209.85.210.173]) by imf13.hostedemail.com (Postfix) with ESMTP id F3F2D20013 for ; Sat, 8 Oct 2022 03:50:46 +0000 (UTC) Received: by mail-pf1-f173.google.com with SMTP id 204so6449564pfx.10 for ; Fri, 07 Oct 2022 20:50:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org; s=google; h=content-disposition:mime-version:message-id:subject:cc:to:from:date :from:to:cc:subject:date:message-id:reply-to; bh=/+M2MWnKezzvwUdnzvMnzBe5u7rJCxF/Jt+qZLDkYO0=; b=FTiUCKipmqUFH72GOvNGAiS4z04PbOMknPHSePECxyT+NR1MKehdmNkDokls+RTwtz 36ZKjqvAgPt8zH/PagzHgUWgsK7jRV+Fodw+XGTQ49lxGfaN2UCRznQ1vjEUvfGAJQxE GFWrUL9ion4oE/GNeI8pk6ab24JqoBKXYgp6c= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-disposition:mime-version:message-id:subject:cc:to:from:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=/+M2MWnKezzvwUdnzvMnzBe5u7rJCxF/Jt+qZLDkYO0=; b=VNDB/jxbjDv1FVMMb8bM2l51AE8I0B019K7l7zt7xcTJG2dBeWI5i+2/HpRo6cZqln rLPOcfzCsrYyRdvj3SqtV0pTMQgNayhu8MEY2rUDJOD2EvFGJjXrVEh8vS2l0+Uj+Gi7 dVGMMCi6giYfMmKdyepa4wskogVLMSYMHvducMb212hwYNfe5/RCjQ4g6ypgvH8DdEMe jsKkRZGnTnl9jWWGpE8lBfO38n5ZN+ZMN8DRQe4UZMYwkGoatocvWkEINhkDLCm6wQLg pI3QTJPBo6w7f6gi6KWQ2Y1CZ87s4TunEifeJbdBDut3B/PhYbmfkOXxaMfYz6MAkxF6 VJ1A== X-Gm-Message-State: ACrzQf2g7APdmD8PNUVeCmIvto9ZTaoMzLDPpJJwtVpxYDj2+EQNPZbR 5iYXVXS/O5qsZHReqDVQziAzmQ== X-Google-Smtp-Source: AMsMyM4VVDsl7sTfR6BuaZGaWhNrchqMetZXBFqCtxdCKjUBjOregElVi6yPdvP6PdPNshZGkoA99Q== X-Received: by 2002:a63:f806:0:b0:439:d86e:1f6e with SMTP id n6-20020a63f806000000b00439d86e1f6emr7461413pgh.46.1665201045645; Fri, 07 Oct 2022 20:50:45 -0700 (PDT) Received: from www.outflux.net (smtp.outflux.net. [198.145.64.163]) by smtp.gmail.com with ESMTPSA id w2-20020a1709026f0200b0017f5ba1fffasm2217544plk.297.2022.10.07.20.50.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 07 Oct 2022 20:50:44 -0700 (PDT) Date: Fri, 7 Oct 2022 20:50:43 -0700 From: Kees Cook To: "Jason A. Donenfeld" Cc: linux-kernel@vger.kernel.org, patches@lists.linux.dev, Andreas Noever , Andrew Morton , Andy Shevchenko , Borislav Petkov , Catalin Marinas , Christoph =?iso-8859-1?Q?B=F6hmwalder?= , Christoph Hellwig , Christophe Leroy , Daniel Borkmann , Dave Airlie , Dave Hansen , "David S. Miller" , Eric Dumazet , Florian Westphal , Greg Kroah-Hartman , "H. Peter Anvin" , Heiko Carstens , Helge Deller , Herbert Xu , Huacai Chen , Hugh Dickins , Jakub Kicinski , "James E. J. Bottomley" , Jan Kara , Jason Gunthorpe , Jens Axboe , Johannes Berg , Jonathan Corbet , Jozsef Kadlecsik , KP Singh , Marco Elver , Mauro Carvalho Chehab , Michael Ellerman , Pablo Neira Ayuso , Paolo Abeni , Peter Zijlstra , Richard Weinberger , Russell King , Theodore Ts'o , Thomas Bogendoerfer , Thomas Gleixner , Thomas Graf , Ulf Hansson , Vignesh Raghavendra , WANG Xuerui , Will Deacon , Yury Norov , dri-devel@lists.freedesktop.org, kasan-dev@googlegroups.com, kernel-janitors@vger.kernel.org, linux-arm-kernel@lists.infradead.org, linux-block@vger.kernel.org, linux-crypto@vger.kernel.org, linux-doc@vger.kernel.org, linux-fsdevel@vger.kernel.org, linux-media@vger.kernel.org, linux-mips@vger.kernel.org, linux-mm@kvack.org, linux-mmc@vger.kernel.org, linux-mtd@lists.infradead.org, linux-nvme@lists.infradead.org, linux-parisc@vger.kernel.org, linux-rdma@vger.kernel.org, linux-s390@vger.kernel.org, linux-um@lists.infradead.org, linux-usb@vger.kernel.org, linux-wireless@vger.kernel.org, linuxppc-dev@lists.ozlabs.org, loongarch@lists.linux.dev, netdev@vger.kernel.org, sparclinux@vger.kernel.org, x86@kernel.org, Jan Kara Subject: Re: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible Message-ID: <53DD0148-ED15-4294-8496-9E4B4C7AD061@chromium.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1665201047; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding:in-reply-to: references:dkim-signature; bh=/+M2MWnKezzvwUdnzvMnzBe5u7rJCxF/Jt+qZLDkYO0=; b=3axvXgyoC/6iyxumIqlO5PvP6lSeM/N/t0gR9zkRs3QbTQLb8jTdIwO8QN/gbg4wegRm6g Aoj4Bz6sks240nr28kpFKjVVBydJfk+sXO7JYFpEPBxw52dJzewZ6vMHwmPZvTpAsPvjxI m0ESVHVxjQDB8GdK1TQaRGG1z8OG3Ws= ARC-Authentication-Results: i=1; imf13.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=FTiUCKip; spf=pass (imf13.hostedemail.com: domain of keescook@chromium.org designates 209.85.210.173 as permitted sender) smtp.mailfrom=keescook@chromium.org; dmarc=pass (policy=none) header.from=chromium.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1665201047; a=rsa-sha256; cv=none; b=r0fP8SjYL1Hfb8Tk2lsrG9uOCqI1NCSqw6bjcKxQ2FwyEnH3vhlOMmKScblyjT8XTt5ops /4fV4RaB68Bfmf1M7NIEoNyMUF7jc4vE+D62Cq1AzOvVmvsryuzXA9my1tm+S2xEt/B1h+ zI1KbUvYZGFHim5Sdicvv58uq9UU/6Y= X-Rspam-User: X-Rspamd-Server: rspam11 X-Rspamd-Queue-Id: F3F2D20013 X-Stat-Signature: 138i81c4cb6afzuudrb3psy91sg3weik Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=FTiUCKip; spf=pass (imf13.hostedemail.com: domain of keescook@chromium.org designates 209.85.210.173 as permitted sender) smtp.mailfrom=keescook@chromium.org; dmarc=pass (policy=none) header.from=chromium.org X-HE-Tag: 1665201046-138731 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: [resending because I failed to CC] On October 7, 2022 7:21:28 PM PDT, "Jason A. Donenfeld" wrote: >On Fri, Oct 07, 2022 at 03:47:44PM -0700, Kees Cook wrote: >> On Fri, Oct 07, 2022 at 12:01:03PM -0600, Jason A. Donenfeld wrote: >> > Rather than incurring a division or requesting too many random bytes for >> > the given range, use the prandom_u32_max() function, which only takes >> > the minimum required bytes from the RNG and avoids divisions. >> >> I actually meant splitting the by-hand stuff by subsystem, but nearly >> all of these can be done mechanically too, so it shouldn't be bad. Notes >> below... > >Oh, cool, more coccinelle. You're basically giving me a class on these >recipes. Much appreciated. You're welcome! This was a fun exercise. :) > >> > [...] >> > diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c >> > index 92bcc1768f0b..87203429f802 100644 >> > --- a/arch/arm64/kernel/process.c >> > +++ b/arch/arm64/kernel/process.c >> > @@ -595,7 +595,7 @@ unsigned long __get_wchan(struct task_struct *p) >> > unsigned long arch_align_stack(unsigned long sp) >> > { >> > if (!(current->personality & ADDR_NO_RANDOMIZE) && randomize_va_space) >> > - sp -= get_random_int() & ~PAGE_MASK; >> > + sp -= prandom_u32_max(PAGE_SIZE); >> > return sp & ~0xf; >> > } >> > >> >> @mask@ >> expression MASK; >> @@ >> >> - (get_random_int() & ~(MASK)) >> + prandom_u32_max(MASK) > >Not quite! PAGE_MASK != PAGE_SIZE. In this case, things get a litttttle >more complicated where you can do: > >get_random_int() & MASK == prandom_u32_max(MASK + 1) >*only if all the top bits of MASK are set* That is, if MASK one less Oh whoops! Yes, right, I totally misread SIZE as MASK. >than a power of two. Or if MASK & (MASK + 1) == 0. > >(If those top bits aren't set, you can technically do >prandom_u32_max(MASK >> n + 1) << n. That'd be a nice thing to work out. >But yeesh, maybe a bit much for the time being and probably a bit beyond >coccinelle.) > >This case here, though, is a bit more special, where we can just rely on >an obvious given kernel identity. Namely, PAGE_MASK == ~(PAGE_SIZE - 1). >So ~PAGE_MASK == PAGE_SIZE - 1. >So get_random_int() & ~PAGE_MASK == prandom_u32_max(PAGE_SIZE - 1 + 1). >So get_random_int() & ~PAGE_MASK == prandom_u32_max(PAGE_SIZE). > >And most importantly, this makes the code more readable, since everybody >knows what bounding by PAGE_SIZE means, where as what on earth is >happening with the &~PAGE_MASK thing. So it's a good change. I'll try to >teach coccinelle about that special case. Yeah, it should be possible to just check for the literal. > > > >> > diff --git a/arch/loongarch/kernel/vdso.c b/arch/loongarch/kernel/vdso.c >> > index f32c38abd791..8c9826062652 100644 >> > --- a/arch/loongarch/kernel/vdso.c >> > +++ b/arch/loongarch/kernel/vdso.c >> > @@ -78,7 +78,7 @@ static unsigned long vdso_base(void) >> > unsigned long base = STACK_TOP; >> > >> > if (current->flags & PF_RANDOMIZE) { >> > - base += get_random_int() & (VDSO_RANDOMIZE_SIZE - 1); >> > + base += prandom_u32_max(VDSO_RANDOMIZE_SIZE); >> > base = PAGE_ALIGN(base); >> > } >> > >> >> @minus_one@ >> expression FULL; >> @@ >> >> - (get_random_int() & ((FULL) - 1) >> + prandom_u32_max(FULL) > >Ahh, well, okay, this is the example I mentioned above. Only works if >FULL is saturated. Any clever way to get coccinelle to prove that? Can >it look at the value of constants? I'm not sure if Cocci will do that without a lot of work. The literals trick I used below would need a lot of fanciness. :) > >> >> > diff --git a/arch/parisc/kernel/vdso.c b/arch/parisc/kernel/vdso.c >> > index 63dc44c4c246..47e5960a2f96 100644 >> > --- a/arch/parisc/kernel/vdso.c >> > +++ b/arch/parisc/kernel/vdso.c >> > @@ -75,7 +75,7 @@ int arch_setup_additional_pages(struct linux_binprm *bprm, >> > >> > map_base = mm->mmap_base; >> > if (current->flags & PF_RANDOMIZE) >> > - map_base -= (get_random_int() & 0x1f) * PAGE_SIZE; >> > + map_base -= prandom_u32_max(0x20) * PAGE_SIZE; >> > >> > vdso_text_start = get_unmapped_area(NULL, map_base, vdso_text_len, 0, 0); >> > >> >> These are more fun, but Coccinelle can still do them with a little >> Pythonic help: >> >> // Find a potential literal >> @literal_mask@ >> expression LITERAL; >> identifier randfunc =~ "get_random_int|prandom_u32|get_random_u32"; >> position p; >> @@ >> >> (randfunc()@p & (LITERAL)) >> >> // Add one to the literal. >> @script:python add_one@ >> literal << literal_mask.LITERAL; >> RESULT; >> @@ >> >> if literal.startswith('0x'): >> value = int(literal, 16) + 1 >> coccinelle.RESULT = cocci.make_expr("0x%x" % (value)) >> elif literal[0] in '123456789': >> value = int(literal, 10) + 1 >> coccinelle.RESULT = cocci.make_expr("%d" % (value)) >> else: >> print("I don't know how to handle: %s" % (literal)) >> >> // Replace the literal mask with the calculated result. >> @plus_one@ >> expression literal_mask.LITERAL; >> position literal_mask.p; >> expression add_one.RESULT; >> identifier FUNC; >> @@ >> >> - (FUNC()@p & (LITERAL)) >> + prandom_u32_max(RESULT) > >Oh that's pretty cool. I can do the saturation check in python, since >`value` holds the parsed result. Neat. It is (at least how I have it here) just the string, so YMMV. > >> > diff --git a/fs/ext2/ialloc.c b/fs/ext2/ialloc.c >> > index 998dd2ac8008..f4944c4dee60 100644 >> > --- a/fs/ext2/ialloc.c >> > +++ b/fs/ext2/ialloc.c >> > @@ -277,8 +277,7 @@ static int find_group_orlov(struct super_block *sb, struct inode *parent) >> > int best_ndir = inodes_per_group; >> > int best_group = -1; >> > >> > - group = prandom_u32(); >> > - parent_group = (unsigned)group % ngroups; >> > + parent_group = prandom_u32_max(ngroups); >> > for (i = 0; i < ngroups; i++) { >> > group = (parent_group + i) % ngroups; >> > desc = ext2_get_group_desc (sb, group, NULL); >> >> Okay, that one is too much for me -- checking that group is never used >> after the assignment removal is likely possible, but beyond my cocci >> know-how. :) > >Yea this is a tricky one, which I initially didn't do by hand, but Jan >seemed fine with it, and it's clear if you look at it. Trixy cocci >indeed. I asked on the Cocci list[1], since by the time I got to the end of your "by hand" patch I *really* wanted to have it work. I was so close! > >> > diff --git a/lib/test_hexdump.c b/lib/test_hexdump.c >> > index 0927f44cd478..41a0321f641a 100644 >> > --- a/lib/test_hexdump.c >> > +++ b/lib/test_hexdump.c >> > @@ -208,7 +208,7 @@ static void __init test_hexdump_overflow(size_t buflen, size_t len, >> > static void __init test_hexdump_overflow_set(size_t buflen, bool ascii) >> > { >> > unsigned int i = 0; >> > - int rs = (prandom_u32_max(2) + 1) * 16; >> > + int rs = prandom_u32_max(2) + 1 * 16; >> > >> > do { >> > int gs = 1 << i; >> >> This looks wrong. Cocci says: >> >> - int rs = (get_random_int() % 2 + 1) * 16; >> + int rs = (prandom_u32_max(2) + 1) * 16; > >!! Nice catch. > >Alright, I'll give this a try with more cocci. The big difficulty at the >moment is the power of 2 constant checking thing. If you have any >pointers on that, would be nice. > >Thanks a bunch for the guidance. Sure thing! I was pleased to figure out how to do the python bit. -Kees [1] actually, I don't see it on lore... I will resend it -- Kees Cook