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.9 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH, MAILING_LIST_MULTI,SIGNED_OFF_BY,SPF_HELO_NONE,SPF_PASS 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 11359C10DCE for ; Wed, 18 Mar 2020 03:58:18 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id B305920753 for ; Wed, 18 Mar 2020 03:58:17 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=chromium.org header.i=@chromium.org header.b="OumfWqTU" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org B305920753 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=chromium.org Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 59AF96B0003; Tue, 17 Mar 2020 23:58:17 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 54C2E6B0006; Tue, 17 Mar 2020 23:58:17 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 462D46B0007; Tue, 17 Mar 2020 23:58:17 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0110.hostedemail.com [216.40.44.110]) by kanga.kvack.org (Postfix) with ESMTP id 2B95F6B0003 for ; Tue, 17 Mar 2020 23:58:17 -0400 (EDT) Received: from smtpin13.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id 5410A1F06 for ; Wed, 18 Mar 2020 03:58:17 +0000 (UTC) X-FDA: 76607125434.13.camp81_827d2bd025637 X-HE-Tag: camp81_827d2bd025637 X-Filterd-Recvd-Size: 6727 Received: from mail-pl1-f194.google.com (mail-pl1-f194.google.com [209.85.214.194]) by imf33.hostedemail.com (Postfix) with ESMTP for ; Wed, 18 Mar 2020 03:58:16 +0000 (UTC) Received: by mail-pl1-f194.google.com with SMTP id t3so10566978plz.9 for ; Tue, 17 Mar 2020 20:58:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org; s=google; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=z7lcLg+250SDKVPIG+/IM07n5R0pxQ9ms66NfWg5VgQ=; b=OumfWqTUdHZ8mYN3IN92aUpk1hqZgXXn7HoovDcJnNExjIhv7DHG/PMpJrc71o8ctc XVM87Q/uS+loikqeWIVNU+mLq10GPojjoJmDiXGY6/0krqdg5r1WASU0Gpdveu26ZODW tFt3zb1IQsE1x+3XA8eLlwiqi+1edfkaHU8qo= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=z7lcLg+250SDKVPIG+/IM07n5R0pxQ9ms66NfWg5VgQ=; b=fhxju9vZ0L7gcqYsxYXDuCDj8gU/MXWcZxIgkOMUHfwsVqxTCi+pVrZY0R3boCZw3d LGbUJjM73hUBLxgd3CgJHfuWgvhzfF1U/k8jQ2YvHSsXORFhcrjSHEmOrrstnS/DxG3V uZVyhw9f+K3COFWJX2YTCiq6guQkNdVAiZC5q8O97GTFBTa8PNy8C38TAuyCsAyd+4L9 2dDdjYKndc9VOEg+jKtwHVozxFdPf8y9PdMnsI8T5pXyN1GlQtGNFDTECFSUEouTX1w2 T8e9TB8FtGSlo18fGQSqDidd8jWSGFSA1MutR5wNdeKuG0ywzwCZneqzqfa/SQfVjlek gSoQ== X-Gm-Message-State: ANhLgQ2hOEQ4D6n7QgIwe7Hb76YMcN575oVPo3uE9NLxiRWAn9jJAVcp 373TPREPTZwIY9W8C/u/mLreMA== X-Google-Smtp-Source: ADFU+vuLVlP0sXFJ1l5dIsSDf9nZMne1q9tjJ0BD951FBJZ3coMH6MdcE5qU2YXRhwIiehSrzGx0zA== X-Received: by 2002:a17:902:8603:: with SMTP id f3mr1901661plo.235.1584503895213; Tue, 17 Mar 2020 20:58:15 -0700 (PDT) Received: from www.outflux.net (smtp.outflux.net. [198.145.64.163]) by smtp.gmail.com with ESMTPSA id q71sm748944pjb.5.2020.03.17.20.58.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 17 Mar 2020 20:58:14 -0700 (PDT) Date: Tue, 17 Mar 2020 20:58:12 -0700 From: Kees Cook To: George Spelvin Cc: Dan Williams , linux-mm@kvack.org, Andrew Morton Subject: Re: [PATCH v2] mm/shuffle.c: Fix races in add_to_free_area_random() Message-ID: <202003172057.0EF895C@keescook> 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: <20200318014410.GA2281@SDF.ORG> 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 01:44:10AM +0000, 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 typo: resultint -> resulting > 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 And with Randy's other fix, please consider this: Acked-by: Kees Cook -Kees > 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)) { > + 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 -- Kees Cook