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=-3.9 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SIGNED_OFF_BY,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 09B6BC4332D for ; Fri, 20 Mar 2020 17:58:08 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id B776020663 for ; Fri, 20 Mar 2020 17:58:07 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=chromium.org header.i=@chromium.org header.b="Gb+VloFi" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org B776020663 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 64D296B0003; Fri, 20 Mar 2020 13:58:07 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 5FDB06B0005; Fri, 20 Mar 2020 13:58:07 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 513646B0007; Fri, 20 Mar 2020 13:58:07 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0073.hostedemail.com [216.40.44.73]) by kanga.kvack.org (Postfix) with ESMTP id 3AD206B0003 for ; Fri, 20 Mar 2020 13:58:07 -0400 (EDT) Received: from smtpin21.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay03.hostedemail.com (Postfix) with ESMTP id C0E3E824556B for ; Fri, 20 Mar 2020 17:58:06 +0000 (UTC) X-FDA: 76616499372.21.loaf76_c8f4149b7f35 X-HE-Tag: loaf76_c8f4149b7f35 X-Filterd-Recvd-Size: 6581 Received: from mail-pj1-f67.google.com (mail-pj1-f67.google.com [209.85.216.67]) by imf32.hostedemail.com (Postfix) with ESMTP for ; Fri, 20 Mar 2020 17:58:06 +0000 (UTC) Received: by mail-pj1-f67.google.com with SMTP id l36so2843899pjb.3 for ; Fri, 20 Mar 2020 10:58:06 -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=fVBQl079pSIwG4d+54HU76hyU3xE+a/SVhTeammObo0=; b=Gb+VloFi1O9KIv2W7sd9cSYThUkl1YKMeSXTsda/XZHbAzRvnUvZX1nAyFypdwk+Ym Ds/dsawAGR+Vo5TW4COsWZq8YyuhFaoHA1B0eUcHGICobKg/Vw1kJFTfSDpF5ziGxVZN eksw3RaF9R+kxj88IiQACcAAssQ8ufQ+ogADY= 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=fVBQl079pSIwG4d+54HU76hyU3xE+a/SVhTeammObo0=; b=oY7/mbtpIybPZRQzc3CuZkjUQkGSMK2lDDDKow9SoLvX7/ja/S+JOAYeKnS/6Y+++O 67FMVYx5QryuLGYyXqOej9C5VMvfL97ohHenbGZi1o34aw5LTAGKSVOdmV34044GY+// 5RYlRV79baxRsIsjb9v9ffhNahLEyHq5f1zGTEkM8puliaRt9skX76Qt2A9tJflKBniP m6b1neFS/BcTY4dXH617n4S4zL8jUaySAIKXBMz3mg2zmTuZH9jJZuwL0AV005EdgCfR zHKVEPuauT11s/rGIEiirwdxsv7XJ3uaZXr+5AY3jZAm/HftrOda2yXJr/tiAg6joXb5 4lYQ== X-Gm-Message-State: ANhLgQ0cS5CfTJaQ2XY21bZap7MqrZzDR4KISJWUmK1jxAd6bj9ulcNl dVy42WG0kPGfndKMPtTK1YtLDw== X-Google-Smtp-Source: ADFU+vsFYrMCmTVqEwhg6LTNXq+QmxAOOCyTe1cu54soMQGLoxZwvg7n15hb8LvH7eqku+gAH9rGEQ== X-Received: by 2002:a17:902:6b84:: with SMTP id p4mr9292554plk.15.1584727084961; Fri, 20 Mar 2020 10:58:04 -0700 (PDT) Received: from www.outflux.net (smtp.outflux.net. [198.145.64.163]) by smtp.gmail.com with ESMTPSA id b20sm5955693pff.51.2020.03.20.10.58.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 20 Mar 2020 10:58:03 -0700 (PDT) Date: Fri, 20 Mar 2020 10:58:02 -0700 From: Kees Cook To: George Spelvin Cc: Dan Williams , linux-mm@kvack.org, Andrew Morton , Alexander Duyck , Randy Dunlap Subject: Re: [PATCH v4] mm/shuffle.c: Fix races in add_to_free_area_random() Message-ID: <202003201057.C7A484A3@keescook> References: <20200317135035.GA19442@SDF.ORG> <202003171435.41F7F0DF9@keescook> <20200317230612.GB19442@SDF.ORG> <202003171619.23210A7E0@keescook> <20200318014410.GA2281@SDF.ORG> <20200318203914.GA16083@SDF.ORG> <20200319120522.GA1484@SDF.ORG> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20200319120522.GA1484@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 Thu, Mar 19, 2020 at 12:05:22PM +0000, George Spelvin wrote: > The separate "rand" and "rand_count" variables could get out of > sync with bad results. > > In the worst case, two threads would see rand_count=1 and both > decrement it, resulting in rand_count=255 and rand being filled > with zeros for the next 255 calls. > > Instead, pack them both into a single, atomically updateable, > 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. Because the random bit > buffer is accessed by multiple threads concurrently without > locking, omitting those puts us deep in the land of nasal demons. > The compiler would be free to spill to the static variable in > arbitrarily perverse ways and create hard-to-find bugs. > > (I'm torn between this and just declaring the buffer "volatile". > Linux tends to prefer marking accesses rather than variables, > but in this case, every access to the buffer is volatile. > It makes no difference to the generated code.) > > Third, use long rather than u64. This not only keeps the state > atomically updateable, 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 a second call > to get_random_u*() per 64 bits. The fast path of get_random_u* > is less than the 3*64 = 192 instructions saved, and the slow path > happens every 64 bytes so isn't affected by the change. > > Fourth, make the function inline. It's small, and there's only > one caller (in mm/page_alloc.c:__free_one_page()), so avoid the > function call overhead. > > Fifth, use the msbits of the buffer first (left shift) rather > than the lsbits (right shift). Testing the sign bit produces > slightly smaller/faster code than testing the lsbit. > > I've tried shifting both ways, and copying the desired bit to a > boolean before shifting rather than keeping separate full-width > r and rshift variables, but both produce larger code: > > x86-64 text size > Msbit 42236 > Lsbit 42242 (+6) > Lsbit+bool 42258 (+22) > Msbit+bool 42284 (+52) > > (Since this is straight-line code, size is a good proxy for number > of instructions and execution time. Using READ/WRITE_ONCE instead of > volatile makes no difference.) > > In a perfect world, on x86-64 the fast path would be: > shlq rand(%eip) > jz refill > refill_complete: > jc add_to_tail > > but I don't see how to get gcc to generate that, and this > function isn't worth arch-specific implementation. > > Signed-off-by: George Spelvin > Acked-by: Kees Cook > Acked-by: Dan Williams > Cc: Alexander Duyck > Cc: Randy Dunlap > Cc: Andrew Morton > Cc: linux-mm@kvack.org > --- > v2: Rewrote commit message to explain existing races better. > Made local variables unsigned to avoid (technically undefined) > signed overflow. > v3: Typos fixed, Acked-by, expanded commit message. > v4: Rebase against -next; function has changed from > add_to_free_area_random() to shuffle_pick_tail. Move to > inline function in shuffle.h. > Not sure if it's okay to keep Acked-by: after such a > significant change. Good by me. Thanks! -Kees -- Kees Cook