From patchwork Tue Mar 17 13:50:35 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: George Spelvin X-Patchwork-Id: 11442945 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id AA9821668 for ; Tue, 17 Mar 2020 13:50:49 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 1F2762076A for ; Tue, 17 Mar 2020 13:50:49 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 1F2762076A Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=SDF.ORG Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 507DA6B0005; Tue, 17 Mar 2020 09:50:48 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 4B8EB6B0006; Tue, 17 Mar 2020 09:50:48 -0400 (EDT) X-Original-To: int-list-linux-mm@kvack.org X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 3A8AE6B0007; Tue, 17 Mar 2020 09:50:48 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0254.hostedemail.com [216.40.44.254]) by kanga.kvack.org (Postfix) with ESMTP id 208376B0005 for ; Tue, 17 Mar 2020 09:50:48 -0400 (EDT) Received: from smtpin09.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay01.hostedemail.com (Postfix) with ESMTP id E3119180AD815 for ; Tue, 17 Mar 2020 13:50:47 +0000 (UTC) X-FDA: 76604989734.09.crack85_6e282894264b X-Spam-Summary: 2,0,0,4ac05eedc403c7ca,d41d8cd98f00b204,lkml@sdf.org,,RULES_HIT:41:355:379:800:960:965:966:973:988:989:1260:1277:1312:1313:1314:1345:1431:1437:1516:1518:1519:1534:1542:1593:1594:1595:1596:1711:1730:1747:1777:1792:2005:2195:2196:2199:2200:2393:2553:2559:2562:2895:3138:3139:3140:3141:3142:3353:3622:3865:3866:3867:3868:3870:3871:3872:3874:4321:4385:4390:4395:5007:6261:7903:7904:8603:9036:10004:10400:11026:11473:11658:11914:12043:12114:12296:12297:12438:12517:12519:12555:12895:13146:13230:13439:13846:13895:14096:14097:14181:14394:14721:14819:21080:21324:21451:21627:30012:30045:30054:30056:30064:30070:30090,0,RBL:205.166.94.20:@sdf.org:.lbl8.mailshell.net-64.201.201.201 62.14.0.100,CacheIP:none,Bayesian:0.5,0.5,0.5,Netcheck:none,DomainCache:0,MSF:not bulk,SPF:fn,MSBL:0,DNSBL:none,Custom_rules:0:0:0,LFtime:25,LUA_SUMMARY:none X-HE-Tag: crack85_6e282894264b X-Filterd-Recvd-Size: 3572 Received: from mx.sdf.org (mx.sdf.org [205.166.94.20]) by imf03.hostedemail.com (Postfix) with ESMTP for ; Tue, 17 Mar 2020 13:50:47 +0000 (UTC) Received: from sdf.org (IDENT:lkml@otaku.sdf.org [205.166.94.8]) by mx.sdf.org (8.15.2/8.14.5) with ESMTPS id 02HDoaL0006137 (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256 bits) verified NO); Tue, 17 Mar 2020 13:50:36 GMT Received: (from lkml@localhost) by sdf.org (8.15.2/8.12.8/Submit) id 02HDoZLi000776; Tue, 17 Mar 2020 13:50:35 GMT Date: Tue, 17 Mar 2020 13:50:35 +0000 From: George Spelvin To: Dan Williams , linux-mm@kvack.org Cc: Kees Cook , Andrew Morton , lkml@sdf.org Subject: [PATCH] mm/shuffle.c: optimize add_to_free_area_random() Message-ID: <20200317135035.GA19442@SDF.ORG> MIME-Version: 1.0 Content-Disposition: inline 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: First, use long rather than u64 for the bit buffer type, which is significantly more efficient on 32-bit processors. 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. 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. I've tried a few variants. Keeping random lsbits with a most- significant end marker, or using an explicit bool variable 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 | 21 ++++++++++++--------- 1 file changed, 12 insertions(+), 9 deletions(-) diff --git a/mm/shuffle.c b/mm/shuffle.c index b3fe97fd6654..0e4bf6a8da52 100644 --- a/mm/shuffle.c +++ b/mm/shuffle.c @@ -186,22 +186,25 @@ 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 */ + long r = READ_ONCE(rand), rshift = r << 1;; /* - * The lack of locking is deliberate. If 2 threads race to + * rand holds some random msbits, with the end marked by a 1 bit. + * 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. */ - 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 (r < 0) add_to_free_area(page, area, migratetype); else add_to_free_area_tail(page, area, migratetype); - rand_bits--; - rand >>= 1; }