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=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, 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 A62BEC10DCE for ; Wed, 18 Mar 2020 19:17:28 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 5B41D2072C for ; Wed, 18 Mar 2020 19:17:28 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Je74mNQP" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 5B41D2072C Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id DC13D6B0074; Wed, 18 Mar 2020 15:17:27 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D70AA6B0075; Wed, 18 Mar 2020 15:17:27 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C87536B0078; Wed, 18 Mar 2020 15:17:27 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0071.hostedemail.com [216.40.44.71]) by kanga.kvack.org (Postfix) with ESMTP id B0ABD6B0074 for ; Wed, 18 Mar 2020 15:17:27 -0400 (EDT) Received: from smtpin21.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay01.hostedemail.com (Postfix) with ESMTP id 62A96180AD811 for ; Wed, 18 Mar 2020 19:17:27 +0000 (UTC) X-FDA: 76609441734.21.step43_6d69c1e23533 X-HE-Tag: step43_6d69c1e23533 X-Filterd-Recvd-Size: 5674 Received: from mail-il1-f195.google.com (mail-il1-f195.google.com [209.85.166.195]) by imf47.hostedemail.com (Postfix) with ESMTP for ; Wed, 18 Mar 2020 19:17:26 +0000 (UTC) Received: by mail-il1-f195.google.com with SMTP id p1so9943594ils.5 for ; Wed, 18 Mar 2020 12:17:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=ec+R9A180RPUk/MhoDBdKT7U7sm9RgjstUbw8TrqJpo=; b=Je74mNQPutaYdew4zI+DHKOAjQkWjMNJ3uDeH3QpV3Ehgh+U5tJZ41Yes0ONQC8oYp 1ZFs5bOCoQ2yq7D7dsMdneKz/VF+Q+GEfUWasUkBu70tXwS/Ouc8kTL86Ylsc9VmQQI8 3h4v74uJjr3M4TtxYXWectNql/L9ajl8D4A2xmme+QE+nGqwlclCiNrQ8WZJewD8NK1s mI3hhMGpwwKS6bSk/rZS10/j2Ef9vEPAYI9qDblMdoz0meCerXAnNBj1jewKKXBeEbdn x+faGY6Yf4cejlEkFwVpN+nBTlNZqWALZmtsldpYT2gQUXWiUUOL9XEF9TU5DcJ++ai9 lUbA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=ec+R9A180RPUk/MhoDBdKT7U7sm9RgjstUbw8TrqJpo=; b=ovg1nUZ0VzxgLelhCF04xJC9KOo7qYUtZXsHh6/0eHmD0Ob8xs5YLj2uRObR3MKRSQ ofjZvUo7VPau6IkH5SyE3CMebI09ogMeNh5FA4q4PoTdyhJX8n+6B6sPbgNrblaw8xHq LvW+n0uWZGI7I+4Ao1MrJvoaWg7hHwFnhzKNFbcMOKNPNKtn4ZUZtntbwB7hv4VPFC0p T7Q+OBnbhi7HjcU8jVJhwSEfyZJHBwDhwlcJi+gple6qkGzp9E4/Mpu3rJHIFQnl+W1z H3IK18FZ+ObxFuX1mtxaWISYiKiIfLcvYm381i0/9kjgp969I/YPtzL87FVCpavP58kY wtMA== X-Gm-Message-State: ANhLgQ092/3RRVdt1unX3FMVqR5SzyaAbIJnu+QO6qYWBHhPzmXA4iwb 56Y27d05tI8LYhGFB0SQTJ4XnMaCFnRlYhcV32o= X-Google-Smtp-Source: ADFU+vudS2tp8V6go2e2whqT8MWJOM4zu1+t3Yi7SkdYkDuVumeSVDLjA6B7Zn1NK4zXv+6SQVGQQWDabYBpURaSOW4= X-Received: by 2002:a92:8f91:: with SMTP id r17mr5064951ilk.97.1584559045860; Wed, 18 Mar 2020 12:17:25 -0700 (PDT) MIME-Version: 1.0 References: <20200317135035.GA19442@SDF.ORG> <202003171435.41F7F0DF9@keescook> <20200317230612.GB19442@SDF.ORG> <202003171619.23210A7E0@keescook> <20200318014410.GA2281@SDF.ORG> <20200318183500.GC2281@SDF.ORG> In-Reply-To: <20200318183500.GC2281@SDF.ORG> From: Alexander Duyck Date: Wed, 18 Mar 2020 12:17:14 -0700 Message-ID: Subject: Re: [PATCH v2] mm/shuffle.c: Fix races in add_to_free_area_random() To: George Spelvin Cc: Kees Cook , Dan Williams , linux-mm , Andrew Morton Content-Type: text/plain; charset="UTF-8" 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 11:35 AM George Spelvin wrote: > > 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. Okay, if this is coming out the same regardless I suppose it doesn't matter. I am still not a huge fan of skipping the parenthesis as I feel it is a bit uglier to read but that isn't anything that has to be fixed. > >> } > >> + 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. I was just putting it out there as a possibility. What I have seen in the past is that under some circumstances gcc can be smart enough to interpret that as a "branch on carry". My thought was you are likely having to test the value against itself and then you might be able to make use of shift and carry flag to avoid that. In addition you could get away from having to recast a unsigned value as a signed one in order to perform the bit test.