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 lists.sourceforge.net (lists.sourceforge.net [216.105.38.7]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 57CEDC4332F for ; Thu, 6 Oct 2022 12:33:59 +0000 (UTC) Received: from [127.0.0.1] (helo=sfs-ml-2.v29.lw.sourceforge.com) by sfs-ml-2.v29.lw.sourceforge.com with esmtp (Exim 4.95) (envelope-from ) id 1ogQ4c-00013E-Dx; Thu, 06 Oct 2022 12:33:58 +0000 Received: from [172.30.20.202] (helo=mx.sourceforge.net) by sfs-ml-2.v29.lw.sourceforge.com with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1ogQ4b-000134-5M; Thu, 06 Oct 2022 12:33:57 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=sourceforge.net; s=x; h=In-Reply-To:Content-Type:MIME-Version:References: Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To:Content-Transfer-Encoding: Content-ID:Content-Description:Resent-Date:Resent-From:Resent-Sender: Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=PDyor0OPorRMVekuFSJiAglRmrxBh1riIl1rICqIsks=; b=ZuVkpAJKawZ6R5kgfcTAtuS2S7 /EwcFFWBBD4LndPnFWOQewZPD1sxvQ0dxsK06Usn7y4SzblyuPp7M9sYuLnehr4ynvZ6zlXdHEUdm 64WARJdYzuP5dVUJYQBb5hQrybqobf/T2io/DOyTM2Slksxf5aXhbIBMLVffrVYYMB+Q=; DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=sf.net; s=x ; h=In-Reply-To:Content-Type:MIME-Version:References:Message-ID:Subject:Cc:To :From:Date:Sender:Reply-To:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=PDyor0OPorRMVekuFSJiAglRmrxBh1riIl1rICqIsks=; b=Wa6pPVeu+hJjIDmyYPWNlJn30f v8QFWKDgxbNViZw+mFoG+h0PhVEttspo+Y6i17Rf/Iboukz/Hxxka0FFvpYjuaEOfPaq4pWx2lnt3 ss6i8SS2THzmKky9FF+vZX7+pUFed4BrcMo2BsxgTO9eTo1TbGNK3Qcb8kS2LAXxXK6A=; Received: from dfw.source.kernel.org ([139.178.84.217]) by sfi-mx-1.v28.lw.sourceforge.com with esmtps (TLS1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (Exim 4.95) id 1ogQ4U-00Egt2-Pk; Thu, 06 Oct 2022 12:33:57 +0000 Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id 4BD8A6189D; Thu, 6 Oct 2022 12:33:44 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 84CC2C433D6; Thu, 6 Oct 2022 12:33:28 +0000 (UTC) Authentication-Results: smtp.kernel.org; dkim=pass (1024-bit key) header.d=zx2c4.com header.i=@zx2c4.com header.b="boaVkmFe" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=zx2c4.com; s=20210105; t=1665059607; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=PDyor0OPorRMVekuFSJiAglRmrxBh1riIl1rICqIsks=; b=boaVkmFeWj/P/2mwQH9q1gX7LNlMIfDuuF/jF0E1iusdkGap18NZ9sMOKKXCenUfGu1kBs OsFuQiM99GfLC9GZQ0iQjPl+iTbCo2UXzxz3nN8lhLRAzO97rrmctM7VRTQNz+DRBcdhZZ cSGHfymmDp55cC4uDg3E8k04jFUD4XI= Received: by mail.zx2c4.com (ZX2C4 Mail Server) with ESMTPSA id 2c48390d (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Oct 2022 12:33:26 +0000 (UTC) Date: Thu, 6 Oct 2022 06:33:15 -0600 To: Jan Kara Message-ID: References: <20221005214844.2699-1-Jason@zx2c4.com> <20221005214844.2699-4-Jason@zx2c4.com> <20221006084331.4bdktc2zlvbaszym@quack3> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20221006084331.4bdktc2zlvbaszym@quack3> X-Headers-End: 1ogQ4U-00Egt2-Pk Subject: Re: [f2fs-dev] [PATCH v1 3/5] treewide: use get_random_u32() when possible X-BeenThere: linux-f2fs-devel@lists.sourceforge.net X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: "Jason A. Donenfeld via Linux-f2fs-devel" Reply-To: "Jason A. Donenfeld" Cc: Andrew Lunn , "Darrick J . Wong" , linux-block@vger.kernel.org, Marcelo Ricardo Leitner , dri-devel@lists.freedesktop.org, Andrii Nakryiko , Hans Verkuil , linux-sctp@vger.kernel.org, "Md . Haris Iqbal" , Miquel Raynal , Christoph Hellwig , Andy Gospodarek , Sergey Matyukevich , Rohit Maheshwari , Michael Ellerman , Christophe Leroy , Jozsef Kadlecsik , Nilesh Javali , Jean-Paul Roubelat , Dan Williams , Dick Kennedy , Jay Vosburgh , Potnuri Bharat Teja , Vinay Kumar Yadav , Arend van Spriel , Nicholas Piggin , Igor Mitsyanko , Andy Lutomirski , linux-hams@vger.kernel.org, Thomas Gleixner , Trond Myklebust , "Martin K . Petersen" , Greg Kroah-Hartman , linux-usb@vger.kernel.org, Michael Chan , linux-kernel@vger.kernel.org, Varun Prakash , David Ahern , Chuck Lever , netfilter-devel@vger.kernel.org, linux-crypto@vger.kernel.org, Jiri Olsa , Jan Kara , linux-fsdevel@vger.kernel.org, Andrew Morton , Claudiu Beznea , Sharvari Harisangam , linux-fbdev@vger.kernel.org, linux-doc@vger.kernel.org, Vignesh Raghavendra , linux-wireless@vger.kernel.org, Dave Hansen , Song Liu , Eric Dumazet , target-devel@vger.kernel.org, John Stultz , Stanislav Fomichev , Gregory Greenman , drbd-dev@lists.linbit.com, dev@openvswitch.org, Leon Romanovsky , Helge Deller , Hugh Dickins , James Smart , Anil S Keshavamurthy , Pravin B Shelar , Julian Anastasov , coreteam@netfilter.org, Veaceslav Falico , Yonghong Song , Namjae Jeon , linux-media@vger.kernel.org, Ganapathi Bhat , linux-actions@lists.infradead.org, Simon Horman , Jaegeuk Kim , Mika Westerberg , Lars Ellenberg , OGAWA Hirofumi , Hao Luo , Theodore Ts'o , Stephen Boyd , Jonathan Corbet , Florian Westphal , "David S . Miller" , Jon Maloy , Anna Schumaker , Yehezkel Bernat , Jeff Layton , Haoyue Xu , Heiner Kallweit , Ulf Hansson , Rasmus Villemoes , linux-nvme@lists.infradead.org, Michal Januszewski , linux-mtd@lists.infradead.org, kasan-dev@googlegroups.com, Cong Wang , Thomas Sailer , Ajay Singh , Andy Shevchenko , Sagi Grimberg , Daniel Borkmann , Dennis Dalessandro , linux-rdma@vger.kernel.org, lvs-devel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, "Naveen N . Rao" , Ilya Dryomov , Paolo Abeni , Pablo Neira Ayuso , Marco Elver , Kees Cook , Yury Norov , "James E . J . Bottomley" , Hante Meuleman , Alexandre Torgue , Borislav Petkov , Keith Busch , ceph-devel@vger.kernel.org, Mauro Carvalho Chehab , Franky Lin , linux-nfs@vger.kernel.org, linux-ext4@vger.kernel.org, Wenpeng Liang , Neil Horman , Xinming Hu , linux-mmc@vger.kernel.org, Martin KaFai Lau , linux-xfs@vger.kernel.org, Ying Xue , Manish Rangankar , Andreas =?utf-8?Q?F=C3=A4rber?= , Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= , linux-stm32@st-md-mailman.stormreply.com, Peter Zijlstra , Ayush Sawal , KP Singh , Amitkumar Karwar , linux-mm@kvack.org, Andreas Dilger , Akinobu Mita , "H . Peter Anvin" , Andreas Noever , Jiri Pirko , linux-f2fs-devel@lists.sourceforge.net, Jack Wang , Steffen Klassert , rds-devel@oss.oracle.com, Herbert Xu , linux-scsi@vger.kernel.org, dccp@vger.kernel.org, Richard Weinberger , Russell King , Jason Gunthorpe , SHA-cyfmac-dev-list@infineon.com, Ingo Molnar , Jakub Kicinski , Masami Hiramatsu , John Fastabend , Maxime Coquelin , Manivannan Sadhasivam , Michael Jamet , Kalle Valo , Santosh Shilimkar , Jamal Hadi Salim , linux-raid@vger.kernel.org, Thomas Graf , Hannes Reinecke , Xiubo Li , Dmitry Vyukov , Jens Axboe , cake@lists.bufferbloat.net, brcm80211-dev-list.pdl@broadcom.com, Yishai Hadas , Hideaki YOSHIFUJI , netdev@vger.kernel.org, Vlad Yasevich , Philipp Reisner , Stephen Hemminger , Christoph =?utf-8?Q?B=C3=B6hmwalder?= , Vinod Koul , tipc-discussion@lists.sourceforge.net, dmaengine@vger.kernel.org, Johannes Berg , Sungjong Seo , linuxppc-dev@lists.ozlabs.org Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: linux-f2fs-devel-bounces@lists.sourceforge.net On Thu, Oct 06, 2022 at 10:43:31AM +0200, Jan Kara wrote: > The code here is effectively doing the > > parent_group = prandom_u32_max(ngroups); > > Similarly here we can use prandom_u32_max(ngroups) like: > > if (qstr) { > ... > parent_group = hinfo.hash % ngroups; > } else > parent_group = prandom_u32_max(ngroups); Nice catch. I'll move these to patch #1. > > diff --git a/fs/ext4/mmp.c b/fs/ext4/mmp.c > > index 9af68a7ecdcf..588cb09c5291 100644 > > --- a/fs/ext4/mmp.c > > +++ b/fs/ext4/mmp.c > > @@ -265,7 +265,7 @@ static unsigned int mmp_new_seq(void) > > u32 new_seq; > > > > do { > > - new_seq = prandom_u32(); > > + new_seq = get_random_u32(); > > } while (new_seq > EXT4_MMP_SEQ_MAX); > > OK, here we again effectively implement prandom_u32_max(EXT4_MMP_SEQ_MAX + 1). > Just presumably we didn't want to use modulo here because EXT4_MMP_SEQ_MAX > is rather big and so the resulting 'new_seq' would be seriously > non-uniform. I'm not handling this during this patch set, but if in the course of review we find enough places that want actually uniformly bounded integers, I'll implement efficient rejection sampling to clean up these cases, with something faster and general, and add a new function for it. So far this is the first case to come up, but we'll probably eventually find others. So I'll make note of this. Jason _______________________________________________ Linux-f2fs-devel mailing list Linux-f2fs-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel From mboxrd@z Thu Jan 1 00:00:00 1970 From: "Jason A. Donenfeld via dev" Subject: Re: [f2fs-dev] [PATCH v1 3/5] treewide: use get_random_u32() when possible Date: Thu, 6 Oct 2022 06:33:15 -0600 Message-ID: References: <20221005214844.2699-1-Jason@zx2c4.com> <20221005214844.2699-4-Jason@zx2c4.com> <20221006084331.4bdktc2zlvbaszym@quack3> Reply-To: "Jason A. Donenfeld" Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Return-path: DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 18BE86104C DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 210BB60F3D DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 1C547402BC DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 6C968402A7 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=zx2c4.com; s=20210105; t=1665059607; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=PDyor0OPorRMVekuFSJiAglRmrxBh1riIl1rICqIsks=; b=boaVkmFeWj/P/2mwQH9q1gX7LNlMIfDuuF/jF0E1iusdkGap18NZ9sMOKKXCenUfGu1kBs OsFuQiM99GfLC9GZQ0iQjPl+iTbCo2UXzxz3nN8lhLRAzO97rrmctM7VRTQNz+DRBcdhZZ cSGHfymmDp55cC4uDg3E8k04jFUD4XI= Content-Disposition: inline In-Reply-To: <20221006084331.4bdktc2zlvbaszym@quack3> List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces-yBygre7rU0TnMu66kgdUjQ@public.gmane.org Sender: "dev" To: Jan Kara Cc: Andrew Lunn , "Darrick J . Wong" , linux-block-u79uwXL29TY76Z2rM5mHXA@public.gmane.org, Marcelo Ricardo Leitner , dri-devel-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org, Andrii Nakryiko , Hans Verkuil , linux-sctp-u79uwXL29TY76Z2rM5mHXA@public.gmane.org, "Md . Haris Iqbal" , Miquel Raynal , Christoph Hellwig , Andy Gospodarek , Sergey Matyukevich , Rohit Maheshwari , Michael Ellerman , Christophe Leroy , Jozsef Kadlecsik , Nilesh Javali , Jean-Paul Roubelat , Dan Williams , Dick Kennedy , Jay Vosburgh , Potnuri Bharat Teja On Thu, Oct 06, 2022 at 10:43:31AM +0200, Jan Kara wrote: > The code here is effectively doing the > > parent_group = prandom_u32_max(ngroups); > > Similarly here we can use prandom_u32_max(ngroups) like: > > if (qstr) { > ... > parent_group = hinfo.hash % ngroups; > } else > parent_group = prandom_u32_max(ngroups); Nice catch. I'll move these to patch #1. > > diff --git a/fs/ext4/mmp.c b/fs/ext4/mmp.c > > index 9af68a7ecdcf..588cb09c5291 100644 > > --- a/fs/ext4/mmp.c > > +++ b/fs/ext4/mmp.c > > @@ -265,7 +265,7 @@ static unsigned int mmp_new_seq(void) > > u32 new_seq; > > > > do { > > - new_seq = prandom_u32(); > > + new_seq = get_random_u32(); > > } while (new_seq > EXT4_MMP_SEQ_MAX); > > OK, here we again effectively implement prandom_u32_max(EXT4_MMP_SEQ_MAX + 1). > Just presumably we didn't want to use modulo here because EXT4_MMP_SEQ_MAX > is rather big and so the resulting 'new_seq' would be seriously > non-uniform. I'm not handling this during this patch set, but if in the course of review we find enough places that want actually uniformly bounded integers, I'll implement efficient rejection sampling to clean up these cases, with something faster and general, and add a new function for it. So far this is the first case to come up, but we'll probably eventually find others. So I'll make note of this. Jason 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 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 smtp.lore.kernel.org (Postfix) with ESMTPS id 4526FC433F5 for ; Thu, 6 Oct 2022 12:33:59 +0000 (UTC) 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:In-Reply-To:MIME-Version:References: Message-ID:Subject:Cc:To:From:Date:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=dMeSvHs1mrPa8AWCSyFutQZyUHEO88LYeGwUCrM+Hso=; b=vYpf4GLCsHJhhV FKGaOuL+H7IsP8dkFwZRb0gwnSnL4lvQBdz2YZ02962wzTB/UfAiUOVz+jxvSfRCfyqlLRkOcc7X3 FqyWhNqe7CkTSCqecdx3AY8Ps4YBYp/yI64AqB3m5cD3paM5GGM+rg8DZqJyvOmGZWB5crxopyDic roJcuR7omnnHnAS8CIic9KDRQa45JsFK2KTvQ0zKXg7BSqIODICOJpSnGDN/gw+pOVC7GhS/LiqUo TMDr/LZ5j/U+jTifcA5tkm+H9zD7bq22Vyvp3SxlgdRjIs9Z3spxS90zjGboGg/6r7vsVQETBR5fg uyD0f43d6MyYur0Rd9eQ==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1ogQ4W-002Jqq-37; Thu, 06 Oct 2022 12:33:52 +0000 Received: from dfw.source.kernel.org ([139.178.84.217]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1ogQ4P-002JnD-3R; Thu, 06 Oct 2022 12:33:47 +0000 Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id 4BD8A6189D; Thu, 6 Oct 2022 12:33:44 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 84CC2C433D6; Thu, 6 Oct 2022 12:33:28 +0000 (UTC) Authentication-Results: smtp.kernel.org; dkim=pass (1024-bit key) header.d=zx2c4.com header.i=@zx2c4.com header.b="boaVkmFe" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=zx2c4.com; s=20210105; t=1665059607; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=PDyor0OPorRMVekuFSJiAglRmrxBh1riIl1rICqIsks=; b=boaVkmFeWj/P/2mwQH9q1gX7LNlMIfDuuF/jF0E1iusdkGap18NZ9sMOKKXCenUfGu1kBs OsFuQiM99GfLC9GZQ0iQjPl+iTbCo2UXzxz3nN8lhLRAzO97rrmctM7VRTQNz+DRBcdhZZ cSGHfymmDp55cC4uDg3E8k04jFUD4XI= Received: by mail.zx2c4.com (ZX2C4 Mail Server) with ESMTPSA id 2c48390d (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Oct 2022 12:33:26 +0000 (UTC) Date: Thu, 6 Oct 2022 06:33:15 -0600 From: "Jason A. Donenfeld" To: Jan Kara Cc: Andrew Lunn , "Darrick J . Wong" , Ulf Hansson , dri-devel@lists.freedesktop.org, Andrii Nakryiko , Hans Verkuil , linux-sctp@vger.kernel.org, "Md . Haris Iqbal" , Miquel Raynal , Christoph Hellwig , Andy Gospodarek , Sergey Matyukevich , Rohit Maheshwari , Michael Ellerman , ceph-devel@vger.kernel.org, Christophe Leroy , Jozsef Kadlecsik , Nilesh Javali , Jean-Paul Roubelat , Dick Kennedy , Jay Vosburgh , Potnuri Bharat Teja , Vinay Kumar Yadav , linux-nfs@vger.kernel.org, Nicholas Piggin , Igor Mitsyanko , Andy Lutomirski , linux-hams@vger.kernel.org, Thomas Gleixner , Trond Myklebust , linux-raid@vger.kernel.org, Neil Horman , Hante Meuleman , Greg Kroah-Hartman , linux-usb@vger.kernel.org, Michael Chan , linux-kernel@vger.kernel.org, Varun Prakash , Chuck Lever , netfilter-devel@vger.kernel.org, Masami Hiramatsu , Jiri Olsa , Jan Kara , linux-fsdevel@vger.kernel.org, Lars Ellenberg , linux-media@vger.kernel.org, Claudiu Beznea , Sharvari Harisangam , linux-fbdev@vger.kernel.org, linux-doc@vger.kernel.org, linux-mmc@vger.kernel.org, Dave Hansen , Song Liu , Eric Dumazet , target-devel@vger.kernel.org, John Stultz , Stanislav Fomichev , Gregory Greenman , drbd-dev@lists.linbit.com, dev@openvswitch.org, Leon Romanovsky , Helge Deller , Hugh Dickins , James Smart , Anil S Keshavamurthy , Pravin B Shelar , Julian Anastasov , coreteam@netfilter.org, Veaceslav Falico , Yonghong Song , Namjae Jeon , linux-crypto@vger.kernel.org, Santosh Shilimkar , Ganapathi Bhat , linux-actions@lists.infradead.org, Simon Horman , Jaegeuk Kim , Mika Westerberg , Andrew Morton , OGAWA Hirofumi , Hao Luo , Theodore Ts'o , Stephen Boyd , Dennis Dalessandro , Florian Westphal , Andreas =?utf-8?Q?F=C3=A4rber?= , Jon Maloy , Vlad Yasevich , Anna Schumaker , Yehezkel Bernat , Haoyue Xu , Heiner Kallweit , linux-wireless@vger.kernel.org, Marcelo Ricardo Leitner , Rasmus Villemoes , linux-nvme@lists.infradead.org, Michal Januszewski , linux-mtd@lists.infradead.org, kasan-dev@googlegroups.com, Cong Wang , Thomas Sailer , Ajay Singh , Xiubo Li , Sagi Grimberg , Daniel Borkmann , Jonathan Corbet , linux-rdma@vger.kernel.org, lvs-devel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, "Naveen N . Rao" , Ilya Dryomov , Paolo Abeni , Pablo Neira Ayuso , Marco Elver , Kees Cook , Yury Norov , "James E . J . Bottomley" , Jamal Hadi Salim , KP Singh , Borislav Petkov , Keith Busch , Dan Williams , Mauro Carvalho Chehab , Franky Lin , Arend van Spriel , linux-ext4@vger.kernel.org, Wenpeng Liang , "Martin K . Petersen" , Xinming Hu , linux-stm32@st-md-mailman.stormreply.com, Jeff Layton , linux-xfs@vger.kernel.org, netdev@vger.kernel.org, Ying Xue , Manish Rangankar , "David S . Miller" , Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= , Vignesh Raghavendra , Peter Zijlstra , "H . Peter Anvin" , Alexandre Torgue , Amitkumar Karwar , linux-mm@kvack.org, Andreas Dilger , Ayush Sawal , Andreas Noever , Jiri Pirko , linux-f2fs-devel@lists.sourceforge.net, Jack Wang , Steffen Klassert , rds-devel@oss.oracle.com, Herbert Xu , linux-scsi@vger.kernel.org, dccp@vger.kernel.org, Richard Weinberger , Russell King , Jason Gunthorpe , SHA-cyfmac-dev-list@infineon.com, Ingo Molnar , Jakub Kicinski , John Fastabend , Maxime Coquelin , Manivannan Sadhasivam , Michael Jamet , Kalle Valo , Akinobu Mita , linux-block@vger.kernel.org, dmaengine@vger.kernel.org, Hannes Reinecke , Andy Shevchenko , Dmitry Vyukov , Jens Axboe , cake@lists.bufferbloat.net, brcm80211-dev-list.pdl@broadcom.com, Yishai Hadas , Hideaki YOSHIFUJI , linuxppc-dev@lists.ozlabs.org, David Ahern , Philipp Reisner , Stephen Hemminger , Christoph =?utf-8?Q?B=C3=B6hmwalder?= , Vinod Koul , tipc-discussion@lists.sourceforge.net, Thomas Graf , Johannes Berg , Sungjong Seo , Martin KaFai Lau Subject: Re: [f2fs-dev] [PATCH v1 3/5] treewide: use get_random_u32() when possible Message-ID: References: <20221005214844.2699-1-Jason@zx2c4.com> <20221005214844.2699-4-Jason@zx2c4.com> <20221006084331.4bdktc2zlvbaszym@quack3> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20221006084331.4bdktc2zlvbaszym@quack3> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20221006_053345_248219_606B94D0 X-CRM114-Status: GOOD ( 25.34 ) X-BeenThere: linux-mtd@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Linux MTD discussion mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-mtd" Errors-To: linux-mtd-bounces+linux-mtd=archiver.kernel.org@lists.infradead.org On Thu, Oct 06, 2022 at 10:43:31AM +0200, Jan Kara wrote: > The code here is effectively doing the > > parent_group = prandom_u32_max(ngroups); > > Similarly here we can use prandom_u32_max(ngroups) like: > > if (qstr) { > ... > parent_group = hinfo.hash % ngroups; > } else > parent_group = prandom_u32_max(ngroups); Nice catch. I'll move these to patch #1. > > diff --git a/fs/ext4/mmp.c b/fs/ext4/mmp.c > > index 9af68a7ecdcf..588cb09c5291 100644 > > --- a/fs/ext4/mmp.c > > +++ b/fs/ext4/mmp.c > > @@ -265,7 +265,7 @@ static unsigned int mmp_new_seq(void) > > u32 new_seq; > > > > do { > > - new_seq = prandom_u32(); > > + new_seq = get_random_u32(); > > } while (new_seq > EXT4_MMP_SEQ_MAX); > > OK, here we again effectively implement prandom_u32_max(EXT4_MMP_SEQ_MAX + 1). > Just presumably we didn't want to use modulo here because EXT4_MMP_SEQ_MAX > is rather big and so the resulting 'new_seq' would be seriously > non-uniform. I'm not handling this during this patch set, but if in the course of review we find enough places that want actually uniformly bounded integers, I'll implement efficient rejection sampling to clean up these cases, with something faster and general, and add a new function for it. So far this is the first case to come up, but we'll probably eventually find others. So I'll make note of this. Jason ______________________________________________________ Linux MTD discussion mailing list http://lists.infradead.org/mailman/listinfo/linux-mtd/ 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 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 smtp.lore.kernel.org (Postfix) with ESMTPS id 4BB47C433F5 for ; Thu, 6 Oct 2022 15:02:02 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender:List-Subscribe:List-Help :List-Post:List-Archive:List-Unsubscribe:List-Id:In-Reply-To:Content-Type: MIME-Version:References:Message-ID:Subject:Cc:To:From:Date:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=PDyor0OPorRMVekuFSJiAglRmrxBh1riIl1rICqIsks=; b=qL1C9b7pwDEBx2CmtZ0kCmij6N PxITBZkc6hTXxn7n1m4tR3icFlKkXH6AIXJj1/yk/rFrCuK/se1yEzpJF2XP0eYHUnIIMlFUI4x8J 57DMiwk/DG5uNxAa+3bHemlRhrFwmzoCOzyYHMpTijJDjgR0pirKsJ5NQLEBuwhdKqLOr5ixANh23 dM9q+ChLj99n66YT83OsxxmpLDQBuaJ35jKi1cOwgHCebDushUZyQaCKURuz95J2aiE0mzXRw1iu5 dn3y+EUH96QzgYU6SfjHxS0J4p2qmuod7Ncgg8b0e3YlZBEGqrxLRAIZuiSAtF8RulaJUoPAInMNY SBB4UAWA==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1ogSNq-003C5h-Qn; Thu, 06 Oct 2022 15:01:58 +0000 Received: from dfw.source.kernel.org ([139.178.84.217]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1ogQ4P-002JnD-3R; Thu, 06 Oct 2022 12:33:47 +0000 Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id 4BD8A6189D; Thu, 6 Oct 2022 12:33:44 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 84CC2C433D6; Thu, 6 Oct 2022 12:33:28 +0000 (UTC) Authentication-Results: smtp.kernel.org; dkim=pass (1024-bit key) header.d=zx2c4.com header.i=@zx2c4.com header.b="boaVkmFe" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=zx2c4.com; s=20210105; t=1665059607; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=PDyor0OPorRMVekuFSJiAglRmrxBh1riIl1rICqIsks=; b=boaVkmFeWj/P/2mwQH9q1gX7LNlMIfDuuF/jF0E1iusdkGap18NZ9sMOKKXCenUfGu1kBs OsFuQiM99GfLC9GZQ0iQjPl+iTbCo2UXzxz3nN8lhLRAzO97rrmctM7VRTQNz+DRBcdhZZ cSGHfymmDp55cC4uDg3E8k04jFUD4XI= Received: by mail.zx2c4.com (ZX2C4 Mail Server) with ESMTPSA id 2c48390d (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Oct 2022 12:33:26 +0000 (UTC) Date: Thu, 6 Oct 2022 06:33:15 -0600 From: "Jason A. Donenfeld" To: Jan Kara Cc: Andrew Lunn , "Darrick J . Wong" , Ulf Hansson , dri-devel@lists.freedesktop.org, Andrii Nakryiko , Hans Verkuil , linux-sctp@vger.kernel.org, "Md . Haris Iqbal" , Miquel Raynal , Christoph Hellwig , Andy Gospodarek , Sergey Matyukevich , Rohit Maheshwari , Michael Ellerman , ceph-devel@vger.kernel.org, Christophe Leroy , Jozsef Kadlecsik , Nilesh Javali , Jean-Paul Roubelat , Dick Kennedy , Jay Vosburgh , Potnuri Bharat Teja , Vinay Kumar Yadav , linux-nfs@vger.kernel.org, Nicholas Piggin , Igor Mitsyanko , Andy Lutomirski , linux-hams@vger.kernel.org, Thomas Gleixner , Trond Myklebust , linux-raid@vger.kernel.org, Neil Horman , Hante Meuleman , Greg Kroah-Hartman , linux-usb@vger.kernel.org, Michael Chan , linux-kernel@vger.kernel.org, Varun Prakash , Chuck Lever , netfilter-devel@vger.kernel.org, Masami Hiramatsu , Jiri Olsa , Jan Kara , linux-fsdevel@vger.kernel.org, Lars Ellenberg , linux-media@vger.kernel.org, Claudiu Beznea , Sharvari Harisangam , linux-fbdev@vger.kernel.org, linux-doc@vger.kernel.org, linux-mmc@vger.kernel.org, Dave Hansen , Song Liu , Eric Dumazet , target-devel@vger.kernel.org, John Stultz , Stanislav Fomichev , Gregory Greenman , drbd-dev@lists.linbit.com, dev@openvswitch.org, Leon Romanovsky , Helge Deller , Hugh Dickins , James Smart , Anil S Keshavamurthy , Pravin B Shelar , Julian Anastasov , coreteam@netfilter.org, Veaceslav Falico , Yonghong Song , Namjae Jeon , linux-crypto@vger.kernel.org, Santosh Shilimkar , Ganapathi Bhat , linux-actions@lists.infradead.org, Simon Horman , Jaegeuk Kim , Mika Westerberg , Andrew Morton , OGAWA Hirofumi , Hao Luo , Theodore Ts'o , Stephen Boyd , Dennis Dalessandro , Florian Westphal , Andreas =?utf-8?Q?F=C3=A4rber?= , Jon Maloy , Vlad Yasevich , Anna Schumaker , Yehezkel Bernat , Haoyue Xu , Heiner Kallweit , linux-wireless@vger.kernel.org, Marcelo Ricardo Leitner , Rasmus Villemoes , linux-nvme@lists.infradead.org, Michal Januszewski , linux-mtd@lists.infradead.org, kasan-dev@googlegroups.com, Cong Wang , Thomas Sailer , Ajay Singh , Xiubo Li , Sagi Grimberg , Daniel Borkmann , Jonathan Corbet , linux-rdma@vger.kernel.org, lvs-devel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, "Naveen N . Rao" , Ilya Dryomov , Paolo Abeni , Pablo Neira Ayuso , Marco Elver , Kees Cook , Yury Norov , "James E . J . Bottomley" , Jamal Hadi Salim , KP Singh , Borislav Petkov , Keith Busch , Dan Williams , Mauro Carvalho Chehab , Franky Lin , Arend van Spriel , linux-ext4@vger.kernel.org, Wenpeng Liang , "Martin K . Petersen" , Xinming Hu , linux-stm32@st-md-mailman.stormreply.com, Jeff Layton , linux-xfs@vger.kernel.org, netdev@vger.kernel.org, Ying Xue , Manish Rangankar , "David S . Miller" , Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= , Vignesh Raghavendra , Peter Zijlstra , "H . Peter Anvin" , Alexandre Torgue , Amitkumar Karwar , linux-mm@kvack.org, Andreas Dilger , Ayush Sawal , Andreas Noever , Jiri Pirko , linux-f2fs-devel@lists.sourceforge.net, Jack Wang , Steffen Klassert , rds-devel@oss.oracle.com, Herbert Xu , linux-scsi@vger.kernel.org, dccp@vger.kernel.org, Richard Weinberger , Russell King , Jason Gunthorpe , SHA-cyfmac-dev-list@infineon.com, Ingo Molnar , Jakub Kicinski , John Fastabend , Maxime Coquelin , Manivannan Sadhasivam , Michael Jamet , Kalle Valo , Akinobu Mita , linux-block@vger.kernel.org, dmaengine@vger.kernel.org, Hannes Reinecke , Andy Shevchenko , Dmitry Vyukov , Jens Axboe , cake@lists.bufferbloat.net, brcm80211-dev-list.pdl@broadcom.com, Yishai Hadas , Hideaki YOSHIFUJI , linuxppc-dev@lists.ozlabs.org, David Ahern , Philipp Reisner , Stephen Hemminger , Christoph =?utf-8?Q?B=C3=B6hmwalder?= , Vinod Koul , tipc-discussion@lists.sourceforge.net, Thomas Graf , Johannes Berg , Sungjong Seo , Martin KaFai Lau Subject: Re: [f2fs-dev] [PATCH v1 3/5] treewide: use get_random_u32() when possible Message-ID: References: <20221005214844.2699-1-Jason@zx2c4.com> <20221005214844.2699-4-Jason@zx2c4.com> <20221006084331.4bdktc2zlvbaszym@quack3> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <20221006084331.4bdktc2zlvbaszym@quack3> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20221006_053345_248219_606B94D0 X-CRM114-Status: GOOD ( 25.34 ) X-Mailman-Approved-At: Thu, 06 Oct 2022 08:01:46 -0700 X-BeenThere: linux-nvme@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-nvme" Errors-To: linux-nvme-bounces+linux-nvme=archiver.kernel.org@lists.infradead.org On Thu, Oct 06, 2022 at 10:43:31AM +0200, Jan Kara wrote: > The code here is effectively doing the > > parent_group = prandom_u32_max(ngroups); > > Similarly here we can use prandom_u32_max(ngroups) like: > > if (qstr) { > ... > parent_group = hinfo.hash % ngroups; > } else > parent_group = prandom_u32_max(ngroups); Nice catch. I'll move these to patch #1. > > diff --git a/fs/ext4/mmp.c b/fs/ext4/mmp.c > > index 9af68a7ecdcf..588cb09c5291 100644 > > --- a/fs/ext4/mmp.c > > +++ b/fs/ext4/mmp.c > > @@ -265,7 +265,7 @@ static unsigned int mmp_new_seq(void) > > u32 new_seq; > > > > do { > > - new_seq = prandom_u32(); > > + new_seq = get_random_u32(); > > } while (new_seq > EXT4_MMP_SEQ_MAX); > > OK, here we again effectively implement prandom_u32_max(EXT4_MMP_SEQ_MAX + 1). > Just presumably we didn't want to use modulo here because EXT4_MMP_SEQ_MAX > is rather big and so the resulting 'new_seq' would be seriously > non-uniform. I'm not handling this during this patch set, but if in the course of review we find enough places that want actually uniformly bounded integers, I'll implement efficient rejection sampling to clean up these cases, with something faster and general, and add a new function for it. So far this is the first case to come up, but we'll probably eventually find others. So I'll make note of this. Jason 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 lists.ozlabs.org (lists.ozlabs.org [112.213.38.117]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id EFCF1C433FE for ; Thu, 6 Oct 2022 12:40:10 +0000 (UTC) Received: from boromir.ozlabs.org (localhost [IPv6:::1]) by lists.ozlabs.org (Postfix) with ESMTP id 4Mjrcn4JFCz3chb for ; Thu, 6 Oct 2022 23:40:09 +1100 (AEDT) Authentication-Results: lists.ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=zx2c4.com header.i=@zx2c4.com header.a=rsa-sha256 header.s=20210105 header.b=boaVkmFe; dkim-atps=neutral Authentication-Results: lists.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=kernel.org (client-ip=2604:1380:4641:c500::1; helo=dfw.source.kernel.org; envelope-from=srs0=tiop=2h=zx2c4.com=jason@kernel.org; receiver=) Authentication-Results: lists.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=zx2c4.com header.i=@zx2c4.com header.a=rsa-sha256 header.s=20210105 header.b=boaVkmFe; dkim-atps=neutral Received: from dfw.source.kernel.org (dfw.source.kernel.org [IPv6:2604:1380:4641:c500::1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by lists.ozlabs.org (Postfix) with ESMTPS id 4MjrTR0r3dz2xb4 for ; Thu, 6 Oct 2022 23:33:46 +1100 (AEDT) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id 4BD8A6189D; Thu, 6 Oct 2022 12:33:44 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 84CC2C433D6; Thu, 6 Oct 2022 12:33:28 +0000 (UTC) Authentication-Results: smtp.kernel.org; dkim=pass (1024-bit key) header.d=zx2c4.com header.i=@zx2c4.com header.b="boaVkmFe" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=zx2c4.com; s=20210105; t=1665059607; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=PDyor0OPorRMVekuFSJiAglRmrxBh1riIl1rICqIsks=; b=boaVkmFeWj/P/2mwQH9q1gX7LNlMIfDuuF/jF0E1iusdkGap18NZ9sMOKKXCenUfGu1kBs OsFuQiM99GfLC9GZQ0iQjPl+iTbCo2UXzxz3nN8lhLRAzO97rrmctM7VRTQNz+DRBcdhZZ cSGHfymmDp55cC4uDg3E8k04jFUD4XI= Received: by mail.zx2c4.com (ZX2C4 Mail Server) with ESMTPSA id 2c48390d (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Oct 2022 12:33:26 +0000 (UTC) Date: Thu, 6 Oct 2022 06:33:15 -0600 From: "Jason A. Donenfeld" To: Jan Kara Subject: Re: [f2fs-dev] [PATCH v1 3/5] treewide: use get_random_u32() when possible Message-ID: References: <20221005214844.2699-1-Jason@zx2c4.com> <20221005214844.2699-4-Jason@zx2c4.com> <20221006084331.4bdktc2zlvbaszym@quack3> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <20221006084331.4bdktc2zlvbaszym@quack3> X-Mailman-Approved-At: Thu, 06 Oct 2022 23:38:28 +1100 X-BeenThere: linuxppc-dev@lists.ozlabs.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Linux on PowerPC Developers Mail List List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Andrew Lunn , "Darrick J . Wong" , linux-block@vger.kernel.org, Marcelo Ricardo Leitner , dri-devel@lists.freedesktop.org, Andrii Nakryiko , Hans Verkuil , linux-sctp@vger.kernel.org, "Md . Haris Iqbal" , Miquel Raynal , Christoph Hellwig , Andy Gospodarek , Sergey Matyukevich , Rohit Maheshwari , Jozsef Kadlecsik , Nilesh Javali , Jean-Paul Roubelat , Dan Williams , Dick Kennedy , Jay Vosburgh , Potnuri Bharat Teja , Vinay Kumar Yadav , Arend van Spriel , Nicholas Piggin , Igor Mitsyanko , Andy Lutomirski , linux-hams@vger.kernel.org, Thomas Gleixner , Trond Myklebust , "Martin K . Petersen" , Greg Kroah-Hartman , linux-usb@vger.kernel.org, Michael Chan , linux-kernel@vger.kernel.org, Varun Prakash , David Ahern , Chuck Lever , netfilter-devel@vger.kernel.org, linux-crypto@vger.kernel.org, Jiri Olsa , Jan Kara , linux-fsdevel@vger.kernel.org, Andrew Morton , Claudiu Beznea , Sharvari Harisangam , linux-fbdev@vger.kernel.org, linux-doc@vger.kernel.org, Vignesh Raghavendra , linux-wireless@vger.kernel.org, Dave Hansen , Song Liu , Eric Dumazet , target-devel@vger.kernel.org, John Stultz , Stanislav Fomichev , Gregory Greenman , drbd-dev@lists.linbit.com, dev@openvswitch.org, Leon Romanovsky , Helge Deller , Hugh Dickins , James Smart , Anil S Keshavamurthy , Pravin B Shelar , Julian Anastasov , coreteam@netfilter.org, Veaceslav Falico , Yonghong Song , Namjae Jeon , linux-media@vger.kernel.org, Ganapathi Bhat , linux-actions@lists.infradead.org, Simon Horman , Jaegeuk Kim , Mika Westerberg , Lars Ellenberg , OGAWA Hirofumi , Hao Luo , Theodore Ts'o , Stephen Boyd , Jonathan Corbet , Florian Westphal , "David S . Miller" , Jon Maloy , Anna Schumaker , Yehezkel Bernat , Jeff Layton , Haoyue Xu , Heiner Kallweit , Ulf Hansson , Rasmus Villemoes , linux-nvme@lists.infradead.org, Michal Januszewski , linux-mtd@lists.infradead.org, kasan-dev@googlegroups.com, Cong Wang , Thomas Sailer , Ajay Singh , Andy Shevchenko , Sagi Grimberg , Daniel Borkmann , Dennis Dalessandro , linux-rdma@vger.kernel.org, lvs-devel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, "Naveen N . Rao" , Ilya Dryomov , Paolo Abeni , Pablo Neira Ayuso , Marco Elver , Kees Cook , Yury Norov , "James E . J . Bottomley" , Hante Meuleman , Alexandre Torgue , Borislav Petkov , Keith Busch , ceph-devel@vger.kernel.org, Mauro Carvalho Chehab , Franky Lin , linux-nfs@vger.kernel.org, linux-ext4@vger.kernel.org, Wenpeng Liang , Neil Horman , Xinming Hu , linux-mmc@vger.kernel.org, Martin KaFai Lau , linux-xfs@vger.kernel.org, Ying Xue , Manish Rangankar , Andreas =?utf-8?Q?F=C3=A4rber?= , Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= , linux-stm32@st-md-mailman.stormreply.com, Peter Zijlstra , Ayush Sawal , KP Singh , Amitkumar Karwar , linux-mm@kvack.org, Andreas Dilger , Akinobu Mita , "H . Peter Anvin" , Andreas Noever , Jiri Pirko , linux-f2fs-devel@lists.sourceforge.net, Jack Wang , Steffen Klassert , rds-devel@oss.oracle.com, Herbert Xu , linux-scsi@vger.kernel.org, dccp@vger.kernel.org, Richard Weinberger , Russell King , Jason Gunthorpe , SHA-cyfmac-dev-list@infineon.com, Ingo Molnar , Jakub Kicinski , Masami Hiramatsu , John Fastabend , Maxime Coquelin , Manivannan Sadhasivam , Michael Jamet , Kalle Valo < kvalo@kernel.org>, Santosh Shilimkar , Jamal Hadi Salim , linux-raid@vger.kernel.org, Thomas Graf , Hannes Reinecke , Xiubo Li , Dmitry Vyukov , Jens Axboe , cake@lists.bufferbloat.net, brcm80211-dev-list.pdl@broadcom.com, Yishai Hadas , Hideaki YOSHIFUJI , netdev@vger.kernel.org, Vlad Yasevich , Philipp Reisner , Stephen Hemminger , Christoph =?utf-8?Q?B=C3=B6hmwalder?= , Vinod Koul , tipc-discussion@lists.sourceforge.net, dmaengine@vger.kernel.org, Johannes Berg , Sungjong Seo , linuxppc-dev@lists.ozlabs.org Errors-To: linuxppc-dev-bounces+linuxppc-dev=archiver.kernel.org@lists.ozlabs.org Sender: "Linuxppc-dev" On Thu, Oct 06, 2022 at 10:43:31AM +0200, Jan Kara wrote: > The code here is effectively doing the > > parent_group = prandom_u32_max(ngroups); > > Similarly here we can use prandom_u32_max(ngroups) like: > > if (qstr) { > ... > parent_group = hinfo.hash % ngroups; > } else > parent_group = prandom_u32_max(ngroups); Nice catch. I'll move these to patch #1. > > diff --git a/fs/ext4/mmp.c b/fs/ext4/mmp.c > > index 9af68a7ecdcf..588cb09c5291 100644 > > --- a/fs/ext4/mmp.c > > +++ b/fs/ext4/mmp.c > > @@ -265,7 +265,7 @@ static unsigned int mmp_new_seq(void) > > u32 new_seq; > > > > do { > > - new_seq = prandom_u32(); > > + new_seq = get_random_u32(); > > } while (new_seq > EXT4_MMP_SEQ_MAX); > > OK, here we again effectively implement prandom_u32_max(EXT4_MMP_SEQ_MAX + 1). > Just presumably we didn't want to use modulo here because EXT4_MMP_SEQ_MAX > is rather big and so the resulting 'new_seq' would be seriously > non-uniform. I'm not handling this during this patch set, but if in the course of review we find enough places that want actually uniformly bounded integers, I'll implement efficient rejection sampling to clean up these cases, with something faster and general, and add a new function for it. So far this is the first case to come up, but we'll probably eventually find others. So I'll make note of this. Jason From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by mail19.linbit.com (LINBIT Mail Daemon) with ESMTP id 22EE24206CF for ; Thu, 6 Oct 2022 14:42:16 +0200 (CEST) Date: Thu, 6 Oct 2022 06:33:15 -0600 From: "Jason A. Donenfeld" To: Jan Kara Message-ID: References: <20221005214844.2699-1-Jason@zx2c4.com> <20221005214844.2699-4-Jason@zx2c4.com> <20221006084331.4bdktc2zlvbaszym@quack3> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <20221006084331.4bdktc2zlvbaszym@quack3> Cc: Andrew Lunn , "Darrick J . Wong" , linux-block@vger.kernel.org, Marcelo Ricardo Leitner , dri-devel@lists.freedesktop.org, Andrii Nakryiko , Hans Verkuil , linux-sctp@vger.kernel.org, "Md . Haris Iqbal" , Miquel Raynal , Yehezkel Bernat , Christoph Hellwig , Andy Gospodarek , Sergey Matyukevich , Rohit Maheshwari , Michael Ellerman , Christophe Leroy , Jozsef Kadlecsik , Nilesh Javali , Jean-Paul Roubelat , Dan Williams , Dick Kennedy , Jay Vosburgh , Potnuri Bharat Teja , Vinay Kumar Yadav , Arend van Spriel , Nicholas Piggin , Igor Mitsyanko , Andy Lutomirski , linux-hams@vger.kernel.org, Thomas Gleixner , Trond Myklebust , "Martin K . Petersen" , Greg Kroah-Hartman , linux-usb@vger.kernel.org, Michael Chan , linux-kernel@vger.kernel.org, Varun Prakash , Martin KaFai Lau , David Ahern , Chuck Lever , netfilter-devel@vger.kernel.org, linux-crypto@vger.kernel.org, Jiri Olsa , Jan Kara , linux-fsdevel@vger.kernel.org, Andrew Morton , Claudiu Beznea , Sharvari Harisangam , linux-fbdev@vger.kernel.org, linux-doc@vger.kernel.org, Vignesh Raghavendra , linux-wireless@vger.kernel.org, Dave Hansen , Song Liu , Eric Dumazet , target-devel@vger.kernel.org, John Stultz , Stanislav Fomichev , Gregory Greenman , drbd-dev@lists.linbit.com, dev@openvswitch.org, Leon Romanovsky , Helge Deller , Hugh Dickins , James Smart , Anil S Keshavamurthy , Pravin B Shelar , Julian Anastasov , coreteam@netfilter.org, Veaceslav Falico , Yonghong Song , Namjae Jeon , linux-media@vger.kernel.org, Ganapathi Bhat , linux-actions@lists.infradead.org, Simon Horman , Jaegeuk Kim , Mika Westerberg , Lars Ellenberg , OGAWA Hirofumi , Hao Luo , Theodore Ts'o , Stephen Boyd , Jonathan Corbet , Florian Westphal , "David S . Miller" , Jon Maloy , Anna Schumaker , Jeff Layton , Haoyue Xu , Heiner Kallweit , Ulf Hansson , Rasmus Villemoes , linux-nvme@lists.infradead.org, Michal Januszewski , linux-mtd@lists.infradead.org, kasan-dev@googlegroups.com, Cong Wang , Thomas Sailer , Ajay Singh , Andy Shevchenko , Sagi Grimberg , Daniel Borkmann , Dennis Dalessandro , linux-rdma@vger.kernel.org, lvs-devel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, "Naveen N . Rao" , Ilya Dryomov , Paolo Abeni , Pablo Neira Ayuso , Marco Elver , Kees Cook , Yury Norov , "James E . J . Bottomley" , Hante Meuleman , Alexandre Torgue , Borislav Petkov , Keith Busch , ceph-devel@vger.kernel.org, Mauro Carvalho Chehab , Franky Lin , linux-nfs@vger.kernel.org, linux-ext4@vger.kernel.org, Wenpeng Liang , Neil Horman , Xinming Hu , linux-mmc@vger.kernel.org, SHA-cyfmac-dev-list@infineon.com, linux-xfs@vger.kernel.org, Ying Xue , Manish Rangankar , Andreas =?utf-8?Q?F=C3=A4rber?= , Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= , linux-stm32@st-md-mailman.stormreply.com, Peter Zijlstra , Ayush Sawal , KP Singh , Amitkumar Karwar , linux-mm@kvack.org, Andreas Dilger , Akinobu Mita , "H . Peter Anvin" , Andreas Noever , Jiri Pirko , linux-f2fs-devel@lists.sourceforge.net, Jack Wang , Steffen Klassert , rds-devel@oss.oracle.com, Herbert Xu , linux-scsi@vger.kernel.org, dccp@vger.kernel.org, Richard Weinberger , Russell King , Jason Gunthorpe , Ingo Molnar , Jakub Kicinski , Masami Hiramatsu , John Fastabend , Maxime Coquelin , Manivannan Sadhasivam , Michael Jamet , Kalle Valo , Santosh Shilimkar , Jamal Hadi Salim , linux-raid@vger.kernel.org, Thomas Graf , Hannes Reinecke , Xiubo Li , Dmitry Vyukov , Jens Axboe , cake@lists.bufferbloat.net, brcm80211-dev-list.pdl@broadcom.com, Yishai Hadas , Hideaki YOSHIFUJI , netdev@vger.kernel.org, Vlad Yasevich , Philipp Reisner , Stephen Hemminger , Vinod Koul , tipc-discussion@lists.sourceforge.net, dmaengine@vger.kernel.org, Johannes Berg , Sungjong Seo , linuxppc-dev@lists.ozlabs.org Subject: Re: [Drbd-dev] [f2fs-dev] [PATCH v1 3/5] treewide: use get_random_u32() when possible List-Id: "*Coordination* of development, patches, contributions -- *Questions* \(even to developers\) go to drbd-user, please." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , On Thu, Oct 06, 2022 at 10:43:31AM +0200, Jan Kara wrote: > The code here is effectively doing the > > parent_group = prandom_u32_max(ngroups); > > Similarly here we can use prandom_u32_max(ngroups) like: > > if (qstr) { > ... > parent_group = hinfo.hash % ngroups; > } else > parent_group = prandom_u32_max(ngroups); Nice catch. I'll move these to patch #1. > > diff --git a/fs/ext4/mmp.c b/fs/ext4/mmp.c > > index 9af68a7ecdcf..588cb09c5291 100644 > > --- a/fs/ext4/mmp.c > > +++ b/fs/ext4/mmp.c > > @@ -265,7 +265,7 @@ static unsigned int mmp_new_seq(void) > > u32 new_seq; > > > > do { > > - new_seq = prandom_u32(); > > + new_seq = get_random_u32(); > > } while (new_seq > EXT4_MMP_SEQ_MAX); > > OK, here we again effectively implement prandom_u32_max(EXT4_MMP_SEQ_MAX + 1). > Just presumably we didn't want to use modulo here because EXT4_MMP_SEQ_MAX > is rather big and so the resulting 'new_seq' would be seriously > non-uniform. I'm not handling this during this patch set, but if in the course of review we find enough places that want actually uniformly bounded integers, I'll implement efficient rejection sampling to clean up these cases, with something faster and general, and add a new function for it. So far this is the first case to come up, but we'll probably eventually find others. So I'll make note of this. Jason 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 gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 4359CC433FE for ; Fri, 7 Oct 2022 04:55:08 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 9620810E933; Fri, 7 Oct 2022 04:54:24 +0000 (UTC) Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by gabe.freedesktop.org (Postfix) with ESMTPS id 188CC10E542 for ; Thu, 6 Oct 2022 12:33:45 +0000 (UTC) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id 4BD8A6189D; Thu, 6 Oct 2022 12:33:44 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 84CC2C433D6; Thu, 6 Oct 2022 12:33:28 +0000 (UTC) Authentication-Results: smtp.kernel.org; dkim=pass (1024-bit key) header.d=zx2c4.com header.i=@zx2c4.com header.b="boaVkmFe" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=zx2c4.com; s=20210105; t=1665059607; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=PDyor0OPorRMVekuFSJiAglRmrxBh1riIl1rICqIsks=; b=boaVkmFeWj/P/2mwQH9q1gX7LNlMIfDuuF/jF0E1iusdkGap18NZ9sMOKKXCenUfGu1kBs OsFuQiM99GfLC9GZQ0iQjPl+iTbCo2UXzxz3nN8lhLRAzO97rrmctM7VRTQNz+DRBcdhZZ cSGHfymmDp55cC4uDg3E8k04jFUD4XI= Received: by mail.zx2c4.com (ZX2C4 Mail Server) with ESMTPSA id 2c48390d (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Oct 2022 12:33:26 +0000 (UTC) Date: Thu, 6 Oct 2022 06:33:15 -0600 From: "Jason A. Donenfeld" To: Jan Kara Subject: Re: [f2fs-dev] [PATCH v1 3/5] treewide: use get_random_u32() when possible Message-ID: References: <20221005214844.2699-1-Jason@zx2c4.com> <20221005214844.2699-4-Jason@zx2c4.com> <20221006084331.4bdktc2zlvbaszym@quack3> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <20221006084331.4bdktc2zlvbaszym@quack3> X-Mailman-Approved-At: Fri, 07 Oct 2022 04:54:02 +0000 X-BeenThere: dri-devel@lists.freedesktop.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Direct Rendering Infrastructure - Development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Andrew Lunn , "Darrick J . Wong" , linux-block@vger.kernel.org, Marcelo Ricardo Leitner , dri-devel@lists.freedesktop.org, Andrii Nakryiko , Hans Verkuil , linux-sctp@vger.kernel.org, "Md . Haris Iqbal" , Miquel Raynal , Christoph Hellwig , Andy Gospodarek , Sergey Matyukevich , Rohit Maheshwari , Michael Ellerman , Christophe Leroy , Jozsef Kadlecsik , Nilesh Javali , Jean-Paul Roubelat , Dan Williams , Dick Kennedy , Jay Vosburgh , Potnuri Bharat Teja , Vinay Kumar Yadav , Arend van Spriel , Nicholas Piggin , Igor Mitsyanko , Andy Lutomirski , linux-hams@vger.kernel.org, Thomas Gleixner , Trond Myklebust , "Martin K . Petersen" , Greg Kroah-Hartman , linux-usb@vger.kernel.org, Michael Chan , linux-kernel@vger.kernel.org, Varun Prakash , David Ahern , Chuck Lever , netfilter-devel@vger.kernel.org, linux-crypto@vger.kernel.org, Jiri Olsa , Jan Kara , linux-fsdevel@vger.kernel.org, Andrew Morton , Claudiu Beznea , Sharvari Harisangam , linux-fbdev@vger.kernel.org, linux-doc@vger.kernel.org, Vignesh Raghavendra , linux-wireless@vger.kernel.org, Dave Hansen , Song Liu , Eric Dumazet , target-devel@vger.kernel.org, John Stultz , Stanislav Fomichev , Gregory Greenman , drbd-dev@lists.linbit.com, dev@openvswitch.org, Leon Romanovsky , Helge Deller , Hugh Dickins , James Smart , Anil S Keshavamurthy , Pravin B Shelar , Julian Anastasov , coreteam@netfilter.org, Veaceslav Falico , Yonghong Song , Namjae Jeon , linux-media@vger.kernel.org, Ganapathi Bhat , linux-actions@lists.infradead.org, Simon Horman , Jaegeuk Kim , Mika Westerberg , Lars Ellenberg , OGAWA Hirofumi , Hao Luo , Theodore Ts'o , Stephen Boyd , Jonathan Corbet , Florian Westphal , "David S . Miller" , Jon Maloy , Anna Schumaker , Yehezkel Bernat , Jeff Layton , Haoyue Xu , Heiner Kallweit , Ulf Hansson , Rasmus Villemoes , linux-nvme@lists.infradead.org, Michal Januszewski , linux-mtd@lists.infradead.org, kasan-dev@googlegroups.com, Cong Wang , Thomas Sailer , Ajay Singh , Andy Shevchenko , Sagi Grimberg , Daniel Borkmann , Dennis Dalessandro , linux-rdma@vger.kernel.org, lvs-devel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, "Naveen N . Rao" , Ilya Dryomov , Paolo Abeni , Pablo Neira Ayuso , Marco Elver , Kees Cook , Yury Norov , "James E . J . Bottomley" , Hante Meuleman , Alexandre Torgue , Borislav Petkov , Keith Busch , ceph-devel@vger.kernel.org, Mauro Carvalho Chehab , Franky Lin , linux-nfs@vger.kernel.org, linux-ext4@vger.kernel.org, Wenpeng Liang , Neil Horman , Xinming Hu , linux-mmc@vger.kernel.org, Martin KaFai Lau , linux-xfs@vger.kernel.org, Ying Xue , Manish Rangankar , Andreas =?utf-8?Q?F=C3=A4rber?= , Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= , linux-stm32@st-md-mailman.stormreply.com, Peter Zijlstra , Ayush Sawal , KP Singh , Amitkumar Karwar , linux-mm@kvack.org, Andreas Dilger , Akinobu Mita , "H . Peter Anvin" , Andreas Noever , Jiri Pirko , linux-f2fs-devel@lists.sourceforge.net, Jack Wang , Steffen Klassert , rds-devel@oss.oracle.com, Herbert Xu , linux-scsi@vger.kernel.org, dccp@vger.kernel.org, Richard Weinberger , Russell King , Jason Gunthorpe , SHA-cyfmac-dev-list@infineon.com, Ingo Molnar , Jakub Kicinski , Masami Hiramatsu , John Fastabend , Maxime Coquelin , Manivannan Sadhasivam , Michael Jamet , Kalle Valo , Santosh Shilimkar , Jamal Hadi Salim , linux-raid@vger.kernel.org, Thomas Graf , Hannes Reinecke , Xiubo Li , Dmitry Vyukov , Jens Axboe , cake@lists.bufferbloat.net, brcm80211-dev-list.pdl@broadcom.com, Yishai Hadas , Hideaki YOSHIFUJI , netdev@vger.kernel.org, Vlad Yasevich , Philipp Reisner , Stephen Hemminger , Christoph =?utf-8?Q?B=C3=B6hmwalder?= , Vinod Koul , tipc-discussion@lists.sourceforge.net, dmaengine@vger.kernel.org, Johannes Berg , Sungjong Seo , linuxppc-dev@lists.ozlabs.org Errors-To: dri-devel-bounces@lists.freedesktop.org Sender: "dri-devel" On Thu, Oct 06, 2022 at 10:43:31AM +0200, Jan Kara wrote: > The code here is effectively doing the > > parent_group = prandom_u32_max(ngroups); > > Similarly here we can use prandom_u32_max(ngroups) like: > > if (qstr) { > ... > parent_group = hinfo.hash % ngroups; > } else > parent_group = prandom_u32_max(ngroups); Nice catch. I'll move these to patch #1. > > diff --git a/fs/ext4/mmp.c b/fs/ext4/mmp.c > > index 9af68a7ecdcf..588cb09c5291 100644 > > --- a/fs/ext4/mmp.c > > +++ b/fs/ext4/mmp.c > > @@ -265,7 +265,7 @@ static unsigned int mmp_new_seq(void) > > u32 new_seq; > > > > do { > > - new_seq = prandom_u32(); > > + new_seq = get_random_u32(); > > } while (new_seq > EXT4_MMP_SEQ_MAX); > > OK, here we again effectively implement prandom_u32_max(EXT4_MMP_SEQ_MAX + 1). > Just presumably we didn't want to use modulo here because EXT4_MMP_SEQ_MAX > is rather big and so the resulting 'new_seq' would be seriously > non-uniform. I'm not handling this during this patch set, but if in the course of review we find enough places that want actually uniformly bounded integers, I'll implement efficient rejection sampling to clean up these cases, with something faster and general, and add a new function for it. So far this is the first case to come up, but we'll probably eventually find others. So I'll make note of this. Jason