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.9 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,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 2C208C5ACD6 for ; Tue, 17 Mar 2020 21:44:38 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id BC8E720724 for ; Tue, 17 Mar 2020 21:44:37 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=chromium.org header.i=@chromium.org header.b="iOEqcSFM" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org BC8E720724 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 330476B0007; Tue, 17 Mar 2020 17:44:37 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 2E1836B0008; Tue, 17 Mar 2020 17:44:37 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1F7B76B000A; Tue, 17 Mar 2020 17:44:37 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0061.hostedemail.com [216.40.44.61]) by kanga.kvack.org (Postfix) with ESMTP id 072496B0007 for ; Tue, 17 Mar 2020 17:44:37 -0400 (EDT) Received: from smtpin03.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay05.hostedemail.com (Postfix) with ESMTP id A8633181AC9CB for ; Tue, 17 Mar 2020 21:44:36 +0000 (UTC) X-FDA: 76606183752.03.spade93_4553345702e5f X-HE-Tag: spade93_4553345702e5f X-Filterd-Recvd-Size: 4423 Received: from mail-pf1-f196.google.com (mail-pf1-f196.google.com [209.85.210.196]) by imf01.hostedemail.com (Postfix) with ESMTP for ; Tue, 17 Mar 2020 21:44:36 +0000 (UTC) Received: by mail-pf1-f196.google.com with SMTP id z65so12673805pfz.8 for ; Tue, 17 Mar 2020 14:44:36 -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=Aq2UqUGVTAJAnwjip3MehPq6Zkd0j75vzazeRbm7emE=; b=iOEqcSFMGslt0T2WXe5CRQvPtjfrIqysSlqrnjS/cT0MzW5bfjzbqM2/kvaH9ahOOy vn0ksaqT2v+9/jdPZo/IohZlKVLVwyRQuK7agvCzvNw+OPGQhOYw5p8Eidi9U/mxxUnZ Inqk6PBN7GdCYZoTPgkjmKbIcHNSYMS0tSRf0= 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=Aq2UqUGVTAJAnwjip3MehPq6Zkd0j75vzazeRbm7emE=; b=EtkFMNGYQXVv+FzyuiqNV83VwyAD6fehNmTTauB6oL9UM6fqod3wXoifDrXI5quwB3 V9XCGbajNcRHu2NoqZf0zTqmLK6kDUwJKfeBS2NiUVFHPHfN5eoTXDykJG8xcq0MnnZF ajRErSHkwog8tNRcukANZX9XvmY+6S+JgwOkI2XZBsMbA9CYfuAUQcmaRGXuSVjB5Jb4 MaXxrfFQfYuIa7rr73Ok43o6IpWHpxc7PO6Axq4VN+3Urmg/5QmQyfsmiQ3TBlDa9uSH A0O/4sD4uGE8EENQ0W5dOMLzfSys64yMda+KRtqWNHqAI4iLR1rS8jziVoEsh7ASH8CS 3e1w== X-Gm-Message-State: ANhLgQ0+mezDDnwBV9afdDrHqyJvetzlJe76d/IjjEOgQW4u9ewrrboy r2wi2CIj58QCcj67m4JbH2kF6A== X-Google-Smtp-Source: ADFU+vs4JhxDgtirG0nQfVT2F9VFSX+lydezB/FVLcLM0UJCWbfaAP2FS5D5fMIt4AmYHdAs9mhSwQ== X-Received: by 2002:a62:31c4:: with SMTP id x187mr814644pfx.83.1584481475329; Tue, 17 Mar 2020 14:44:35 -0700 (PDT) Received: from www.outflux.net (smtp.outflux.net. [198.145.64.163]) by smtp.gmail.com with ESMTPSA id l1sm315241pje.9.2020.03.17.14.44.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 17 Mar 2020 14:44:34 -0700 (PDT) Date: Tue, 17 Mar 2020 14:44:33 -0700 From: Kees Cook To: George Spelvin Cc: Dan Williams , linux-mm@kvack.org, Andrew Morton Subject: Re: [PATCH] mm/shuffle.c: optimize add_to_free_area_random() Message-ID: <202003171435.41F7F0DF9@keescook> References: <20200317135035.GA19442@SDF.ORG> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20200317135035.GA19442@SDF.ORG> X-Bogosity: Ham, tests=bogofilter, spamicity=0.000924, 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 01:50:35PM +0000, George Spelvin wrote: > First, use long rather than u64 for the bit buffer type, which > is significantly more efficient on 32-bit processors. Why? This is twice as many get_random_*() calls for 32-bit: it'll save whatever bits it doesn't use. (Speaking to word-sized stores, yes, that makes sense, but see below...) > Second, avoid the need for a separate rand_bits counter. > rand_bits is never more than 63, so there's always room in rand > for a bit to mark the end of the available bits. This makes the > shared state atomically updatable, which makes it a lot easier > to reason about race conditions. What are the race conditions? I had to go look at I see that add_to_free_area_random() is called under __free_one_page() which is under &zone->lock. Would it make more sense to store the randomness per-zone and entirely side-step the issues? > Third, use READ_ONCE and WRITE_ONCE. Without them, the compiler > may spill to the shared static in arbitrarily perverse ways, > and combined with the fact that the code eschews locking, that > is a recipe for hard-to-find bugs. Now, a race might cause a bit > to be used twice, or get_random_long() to be called redundantly, > but it can't summon nasal daemons. All these things might make the results less predictable, too. :) But, yes, if there was deterministic sharing of random values, that'd be bad. But this patch doesn't really solve the "use the same random bits" problem, which is the very thing that might get us into a predictable state. If two zones both call READ_ONCE(), use the same value (eek), and then both call WRITE_ONCE(), one of them wins the write (no big deal). -- Kees Cook