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=-0.8 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=no 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 9D307C10DCE for ; Wed, 18 Mar 2020 18:35:23 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id D2BDD20780 for ; Wed, 18 Mar 2020 18:35:21 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org D2BDD20780 Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=SDF.ORG Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 83AFA6B000E; Wed, 18 Mar 2020 14:35:21 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 7C3876B0074; Wed, 18 Mar 2020 14:35:21 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6B29F6B0078; Wed, 18 Mar 2020 14:35:21 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0164.hostedemail.com [216.40.44.164]) by kanga.kvack.org (Postfix) with ESMTP id 4F73D6B000E for ; Wed, 18 Mar 2020 14:35:21 -0400 (EDT) Received: from smtpin12.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay01.hostedemail.com (Postfix) with ESMTP id F041B180AD81D for ; Wed, 18 Mar 2020 18:35:20 +0000 (UTC) X-FDA: 76609335600.12.books16_4bb6aacdeb658 X-HE-Tag: books16_4bb6aacdeb658 X-Filterd-Recvd-Size: 3315 Received: from mx.sdf.org (mx.sdf.org [205.166.94.20]) by imf25.hostedemail.com (Postfix) with ESMTP for ; Wed, 18 Mar 2020 18:35:20 +0000 (UTC) Received: from sdf.org (IDENT:lkml@otaku.sdf.org [205.166.94.8]) by mx.sdf.org (8.15.2/8.14.5) with ESMTPS id 02IIZ2i2012464 (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256 bits) verified NO); Wed, 18 Mar 2020 18:35:02 GMT Received: (from lkml@localhost) by sdf.org (8.15.2/8.12.8/Submit) id 02IIZ2qf003678; Wed, 18 Mar 2020 18:35:02 GMT Date: Wed, 18 Mar 2020 18:35:00 +0000 From: George Spelvin To: Alexander Duyck Cc: Kees Cook , Dan Williams , linux-mm , Andrew Morton , lkml@sdf.org Subject: Re: [PATCH v2] mm/shuffle.c: Fix races in add_to_free_area_random() Message-ID: <20200318183500.GC2281@SDF.ORG> References: <20200317135035.GA19442@SDF.ORG> <202003171435.41F7F0DF9@keescook> <20200317230612.GB19442@SDF.ORG> <202003171619.23210A7E0@keescook> <20200318014410.GA2281@SDF.ORG> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: 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: On Wed, Mar 18, 2020 at 08:26:06AM -0700, Alexander Duyck wrote: > On Tue, Mar 17, 2020 at 6:44 PM George Spelvin wrote: >> + if (unlikely(rshift == 0)) { >> + r = get_random_long(); >> + rshift = r << 1 | 1; > > You might want to wrap the "r << 1" in parenthesis. Also you could > probably use a + 1 instead of an | 1. I could, but what would it matter? I have just confirmed that all of: x << 1 | 1; (x << 1) + 1; x + x + 1; x + x | 1; 2*x + 1; 2*x | 1; compile to leal 1(%rdi,%rdi), %eax on x86, and two instructions on every other processor I can think of. Since this is concpetually a bit-manipulation operation where carry propagation is undesirable, the logical operation form seems the most natural way to write it. As for the parens, all C programmers are forced to remember that the boolean operators have weirdly low precedence (below < <= == >= >), so there's no risk of confusion. >> } >> + WRITE_ONCE(rand, rshift); >> >> - if (rand & 1) >> + if ((long)r < 0) > > One trick you might be able to get away with here is to actually > compare r to rshift. "If (rshift <= r)" should give you the same > result. This works since what you are essentially doing is just adding > r to itself so if you overflow rshift will be equal to at most r - 1. > However with the addition of the single bit in the rshift == 0 case it > could potentially be equal in the unlikely case of r being all 1's. Er... but why would I want to? On most processors, "branch on sign bit" is a single instruction, and that's the instruction I'm hoping the compiler will generate. That's why I changed the shift direction from the original right (testing the lsbit) to left (testing the msbit): slight code size reduction. Anything else produces larger and slower object code, for no benefit.