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=-6.8 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=ham 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 8CC10C10DCE for ; Wed, 18 Mar 2020 03:54:09 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 4A28A20753 for ; Wed, 18 Mar 2020 03:54:09 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=intel-com.20150623.gappssmtp.com header.i=@intel-com.20150623.gappssmtp.com header.b="wr6gAKxJ" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 4A28A20753 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=intel.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id D17586B0003; Tue, 17 Mar 2020 23:54:08 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id CA0E76B0006; Tue, 17 Mar 2020 23:54:08 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B68666B0007; Tue, 17 Mar 2020 23:54:08 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0065.hostedemail.com [216.40.44.65]) by kanga.kvack.org (Postfix) with ESMTP id 9A5066B0003 for ; Tue, 17 Mar 2020 23:54:08 -0400 (EDT) Received: from smtpin15.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay01.hostedemail.com (Postfix) with ESMTP id A6DB5180AD81A for ; Wed, 18 Mar 2020 03:54:08 +0000 (UTC) X-FDA: 76607114976.15.rail47_5e4fd41f09d00 X-HE-Tag: rail47_5e4fd41f09d00 X-Filterd-Recvd-Size: 7057 Received: from mail-ot1-f66.google.com (mail-ot1-f66.google.com [209.85.210.66]) by imf49.hostedemail.com (Postfix) with ESMTP for ; Wed, 18 Mar 2020 03:54:07 +0000 (UTC) Received: by mail-ot1-f66.google.com with SMTP id s15so24148517otq.8 for ; Tue, 17 Mar 2020 20:54:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=intel-com.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=6WWhqCFQQTzhjAJgWQQuwOsa5gzJl66lJQd6l/vcz6A=; b=wr6gAKxJaLdwX4vBM+uyUrLO4mzqQmIEqxSNUuIanXDaknJf3HZvuLEtgRvONuwbK/ D4XLjzwirw8+d3dqi1SlRrwnJZPE/6YKViErS6h1lnd7VIdcdyeQtAMT+6Qa202LaQ/p gzxVTq5Vs9zkgS4KPuiuGHrjYGw6Xu8GSNPnfz3BdxBl7GTQ5lbxZa9Ce8oQjkilo9ON utYHtU+DyXPMCbP7pCC8itFBBmezF5apeXftfKM+2xpyO1WoZGLfEIwtvJEc2BhndaR4 +qFZ9EziwOA4/xREfuwKVG4/UmR3csx2jLRwcCy+ZdH3uDkkjQtt8nLRjfZnwdo6f7lD 6n7g== 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=6WWhqCFQQTzhjAJgWQQuwOsa5gzJl66lJQd6l/vcz6A=; b=nmbZSBnlrkk9AuLejmJFWkJdMQJRXD59rmKOGLJTakK3beMvyCKY2Q4bkSJJaPr+rp GzN9FptG/vXk/yJ44K4LMxxjfwUPYKfa5xU+60cMzzxSiN2n9/xooEFuenHFewn9iK3y Pb0bXCOaSOGeDoOKrpxq20owUxKVXsFqYnjORPLHxF5pipE+19yASkB/Z6h9v0DfKUg8 1TFZJurRjWGbOGIcYqpqZx1nLVCx8Yh4G2bkbp7xDfKkf2B3CX3YY1zUYyJcrWQ9W4HU N8h5YbJH4gSm07LE5o7oR/Au1UrsAftnf4b668SVtBG95MC8XJPDX4Zr+GsIW1BD4cru blcg== X-Gm-Message-State: ANhLgQ1LOlQcGcYxyDYACJrqDiTqzQL4dF4SPbNRuSNf5onZyCL5x/cQ i2bmtix8ASobjHvcMUJkNK+uDN7jtXGn+VWEK+cCTsq060I= X-Google-Smtp-Source: ADFU+vs5Xfk80fRHfj7rVJvNCaEDe0jZKhBqep9kKZ9JUqNhkMD8K9cCzLE4KzkvRqJvuEp1jUnhM4J+dj4XaobV2uw= X-Received: by 2002:a9d:60b:: with SMTP id 11mr2204428otn.126.1584503646702; Tue, 17 Mar 2020 20:54:06 -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> In-Reply-To: <20200318014410.GA2281@SDF.ORG> From: Dan Williams Date: Tue, 17 Mar 2020 20:53:55 -0700 Message-ID: Subject: Re: [PATCH v2] mm/shuffle.c: Fix races in add_to_free_area_random() To: George Spelvin Cc: Kees Cook , 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 Tue, Mar 17, 2020 at 6:44 PM George Spelvin wrote: > > The old code had separate "rand" and "rand_count" variables, > which could get out of sync with bad results. > > In the worst case, two threads would see rand_count == 1 and > both decrement it, resultint in rand_count = 255 and rand being > filled with zeros for the next 255 calls. > > Instead, pack them both into a single, atomically updatable, > variable. This makes it a lot easier to reason about race > conditions. They are still there - the code deliberately eschews > locking - but basically harmless on the rare occasions that > they happen. > > Second, use READ_ONCE and WRITE_ONCE. Without them, we are deep > in the land of nasal demons. The compiler would be free to spill > temporaries to the static variables in arbitrary perverse ways > and create hard-to-find bugs. > > (Alternatively, we could declare the static variable "volatile", > one of the few places in the Linux kernel that would be correct, > but it would probably annoy Linus.) > > Third, use long rather than u64. This not only keeps the > state atomically updatable, it also speeds up the fast path > on 32-bit machines. Saving at least three instructions on > the fast path (one load, one add-with-carry, and one store) > is worth exchanging one call to get_random_u64 for two > calls to get_random_u32. The fast path of get_random_* is > less than the 3*64 = 192 instructions saved, and the slow > path happens every 64 bytes so isn't affectrd by the change. > > I've tried a few variants. Keeping random lsbits with > a most-significant end marker, and using an explicit bool > flag rather than testing r both increase code size slightly. > > x86_64 i386 > This code 94 95 > Explicit bool 103 99 > Lsbits 99 101 > Both 96 100 > > Signed-off-by: George Spelvin > Cc: Dan Williams > Cc: Kees Cook > Cc: Andrew Morton > Cc: linux-mm@kvack.org > --- > mm/shuffle.c | 26 ++++++++++++++++---------- > 1 file changed, 16 insertions(+), 10 deletions(-) > > diff --git a/mm/shuffle.c b/mm/shuffle.c > index e0ed247f8d90..4ba3ba84764d 100644 > --- a/mm/shuffle.c > +++ b/mm/shuffle.c > @@ -186,22 +186,28 @@ void __meminit __shuffle_free_memory(pg_data_t *pgdat) > void add_to_free_area_random(struct page *page, struct free_area *area, > int migratetype) > { > - static u64 rand; > - static u8 rand_bits; > + static long rand; /* 0..BITS_PER_LONG-1 buffered random bits */ > + unsigned long r = READ_ONCE(rand), rshift = r << 1;; > > /* > - * The lack of locking is deliberate. If 2 threads race to > - * update the rand state it just adds to the entropy. > + * rand holds some random msbits, with a 1 bit appended, followed > + * by zero-padding in the lsbits. This allows us to maintain > + * the pre-generated bits and the count of bits in a single, > + * atomically updatable, variable. > + * > + * The lack of locking is deliberate. If two threads race to > + * update the rand state it just adds to the entropy. The > + * worst that can happen is a random bit is used twice, or > + * get_random_long is called redundantly. > */ > - if (rand_bits == 0) { > - rand_bits = 64; > - rand = get_random_u64(); > + if (unlikely(rshift == 0)) { I had the impression that unless unlikely is "mostly never" then it can do more harm than good. Is a branch guaranteed to be taken every BITS_PER_LONG'th occurrence really a candidate for unlikely() annotation? Otherwise this change looks good to me. > + r = get_random_long(); > + rshift = r << 1 | 1; > } > + WRITE_ONCE(rand, rshift); > > - if (rand & 1) > + if ((long)r < 0) > add_to_free_area(page, area, migratetype); > else > add_to_free_area_tail(page, area, migratetype); > - rand_bits--; > - rand >>= 1; > } > -- > 2.26.0.rc2