From patchwork Tue Dec 18 04:23:55 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dan Williams X-Patchwork-Id: 10734795 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7609C6C2 for ; Tue, 18 Dec 2018 04:36:35 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 6595E2A77F for ; Tue, 18 Dec 2018 04:36:35 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 59EBF2A785; Tue, 18 Dec 2018 04:36:35 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.9 required=2.0 tests=BAYES_00,MAILING_LIST_MULTI, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id BDDFC2A77F for ; Tue, 18 Dec 2018 04:36:34 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CE6408E0008; Mon, 17 Dec 2018 23:36:33 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id C95E88E0007; Mon, 17 Dec 2018 23:36:33 -0500 (EST) 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 BADD58E0008; Mon, 17 Dec 2018 23:36:33 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-pf1-f198.google.com (mail-pf1-f198.google.com [209.85.210.198]) by kanga.kvack.org (Postfix) with ESMTP id 7C8A78E0007 for ; Mon, 17 Dec 2018 23:36:33 -0500 (EST) Received: by mail-pf1-f198.google.com with SMTP id d18so14077333pfe.0 for ; Mon, 17 Dec 2018 20:36:33 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-original-authentication-results:x-gm-message-state:subject:from :to:cc:date:message-id:in-reply-to:references:user-agent :mime-version:content-transfer-encoding; bh=t8gmx1MsSVXZhGWKv7RuEJqZ2UQovoSqwCwKG1ArY1c=; b=bdoP48eATmUpumL/ygFbrdIDhQRsF6rqcIoNbWh+DmL01iyYL7LdjelllZEtHrBNV/ 0eKQ324oihr4SrAZfjuCtEpzfFAk0P2sXYTGV19YmctfvLX3wlc9CYQ4MiDLGR+Rx0N4 jHt5T2Oq5vLc+33NpmDQZ3EF6JF+ZZ7avqdjysXIDwhSv8cjgnk5saxhEwDyQidVDJHH 3ihtzOkvSipjRDgqSFb2RN0DMxAtWaYefZLr7srhAePaL7nMcjW95q85ID+b/F+ZPdtv os2OEzh2PBwiGz1iMCdCuJRCVV235an3ZZXS4eGadEqqu8pREEYzBoUjR7jj8eBtzRk8 Ekxw== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dan.j.williams@intel.com designates 134.134.136.20 as permitted sender) smtp.mailfrom=dan.j.williams@intel.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com X-Gm-Message-State: AA+aEWbpeIuwWWJ/lfAjfJbAwouasCd5FW1ZoEuzkzL6/MEtgM6NgW3W FZh8S/aVzyICvh3Avlg0dXGe2mUXMRcE6smXB4wmSyZ8tPZrn/KyGKK3JsyR6VdidrXK2fkqjTw yLYkSDBL6/UNlMUoNb96X+xSBNFrBriPGMPt9doxfSa2H/sx7n8A3fjlTD4BkSPAP9g== X-Received: by 2002:a62:5884:: with SMTP id m126mr15260590pfb.177.1545107793130; Mon, 17 Dec 2018 20:36:33 -0800 (PST) X-Google-Smtp-Source: AFSGD/U4G3Y3XBiro+PlLz8+J/OztuIvPAqTA6KMN1cuD4xI5Ds/OAb//7BvG3t9BfmbQB+ehJRC X-Received: by 2002:a62:5884:: with SMTP id m126mr15260572pfb.177.1545107792389; Mon, 17 Dec 2018 20:36:32 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1545107792; cv=none; d=google.com; s=arc-20160816; b=hMTOrR0uMLDvpDwoDPxjwTlJbeIG3nz0RXACk5uLXF7Ep7L6NqtRK3p9Sm7xBQ54f/ YgVtvDX/EfL+7/x5NilbhFIjEiB/KlGQvadSPz0Qia10gvueuGn1mai7ZQllS6dv5r8v 4MCXLk1cCOUIL292veEducULkwXnEPjfkHlJEUek/Fc51QIEBy2KPXai1IP/IaujW2Ml huJ7g6UuPsCUHFSylLRIjKXTK6ilziO/LPXQUhUGhcrbutqPmftIOQtNTOZ09DANkViw OwFg+HO/cR5TD5utfrYGRyq7Bm0+HH8KuaNR8eDAJEQzBJLJ6VgkQB7PWPGlbjZ5CU3f oWwQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:user-agent:references :in-reply-to:message-id:date:cc:to:from:subject; bh=t8gmx1MsSVXZhGWKv7RuEJqZ2UQovoSqwCwKG1ArY1c=; b=Fk6dMCprVBDfIdWBY0xbK67IhfonUj2yzReCAoPzUdr2BdA28JRsAqMkGaUVCLPWQk LejgnQsiiQgb8PITFbV9VvtgSf2Y9+kvVMZ28sd4C3tyjLmVLmVy4ELBuKVuu/NqiuS3 YT1oISUTvmANsBHH9ejnj9NmaWN3TuRegFTUFjkH6fL1YxAQH0QS/cYUF2i6bgBGFLY+ 9zTctBfIjA8Z/U5bO2S81n/8ADW/8b6fLSPY0/SLSk7+ZGcD5XoQDYoOhgZj5oY6bsip iEJe7txX1r2Tsie31mcwaLSQ//1VKF6zs+IeNpwF6Zrv2dtx9to70Oa/V27NRR8q/7Cd L+kg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dan.j.williams@intel.com designates 134.134.136.20 as permitted sender) smtp.mailfrom=dan.j.williams@intel.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com Received: from mga02.intel.com (mga02.intel.com. [134.134.136.20]) by mx.google.com with ESMTPS id v14si13414844pfc.76.2018.12.17.20.36.32 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 17 Dec 2018 20:36:32 -0800 (PST) Received-SPF: pass (google.com: domain of dan.j.williams@intel.com designates 134.134.136.20 as permitted sender) client-ip=134.134.136.20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dan.j.williams@intel.com designates 134.134.136.20 as permitted sender) smtp.mailfrom=dan.j.williams@intel.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga008.fm.intel.com ([10.253.24.58]) by orsmga101.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 17 Dec 2018 20:36:31 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.56,367,1539673200"; d="scan'208";a="110266003" Received: from dwillia2-desk3.jf.intel.com (HELO dwillia2-desk3.amr.corp.intel.com) ([10.54.39.16]) by fmsmga008.fm.intel.com with ESMTP; 17 Dec 2018 20:36:30 -0800 Subject: [PATCH v6 6/6] mm: Maintain randomization of page free lists From: Dan Williams To: akpm@linux-foundation.org Cc: Michal Hocko , Kees Cook , Dave Hansen , peterz@infradead.org, linux-mm@kvack.org, x86@kernel.org, linux-kernel@vger.kernel.org, mgorman@suse.de Date: Mon, 17 Dec 2018 20:23:55 -0800 Message-ID: <154510703541.1941238.6053320635908576300.stgit@dwillia2-desk3.amr.corp.intel.com> In-Reply-To: <154510700291.1941238.817190985966612531.stgit@dwillia2-desk3.amr.corp.intel.com> References: <154510700291.1941238.817190985966612531.stgit@dwillia2-desk3.amr.corp.intel.com> User-Agent: StGit/0.18-2-gc94f MIME-Version: 1.0 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: X-Virus-Scanned: ClamAV using ClamSMTP When freeing a page with an order >= shuffle_page_order randomly select the front or back of the list for insertion. While the mm tries to defragment physical pages into huge pages this can tend to make the page allocator more predictable over time. Inject the front-back randomness to preserve the initial randomness established by shuffle_free_memory() when the kernel was booted. The overhead of this manipulation is constrained by only being applied for MAX_ORDER sized pages by default. Cc: Michal Hocko Cc: Kees Cook Cc: Dave Hansen Signed-off-by: Dan Williams --- include/linux/mmzone.h | 10 ++++++++++ include/linux/shuffle.h | 12 ++++++++++++ mm/page_alloc.c | 11 +++++++++-- mm/shuffle.c | 16 ++++++++++++++++ 4 files changed, 47 insertions(+), 2 deletions(-) diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h index 35cc33af87f2..338929647eea 100644 --- a/include/linux/mmzone.h +++ b/include/linux/mmzone.h @@ -98,6 +98,8 @@ extern int page_group_by_mobility_disabled; struct free_area { struct list_head free_list[MIGRATE_TYPES]; unsigned long nr_free; + u64 rand; + u8 rand_bits; }; /* Used for pages not on another list */ @@ -116,6 +118,14 @@ static inline void add_to_free_area_tail(struct page *page, struct free_area *ar area->nr_free++; } +#ifdef CONFIG_SHUFFLE_PAGE_ALLOCATOR +/* Used to preserve page allocation order entropy */ +void add_to_free_area_random(struct page *page, struct free_area *area, + int migratetype); +#else +#define add_to_free_area_random add_to_free_area +#endif + /* Used for pages which are on another list */ static inline void move_to_free_area(struct page *page, struct free_area *area, int migratetype) diff --git a/include/linux/shuffle.h b/include/linux/shuffle.h index a8a168919cb5..8b3941a87c2c 100644 --- a/include/linux/shuffle.h +++ b/include/linux/shuffle.h @@ -29,6 +29,13 @@ static inline void shuffle_zone(struct zone *z, unsigned long start_pfn, return; __shuffle_zone(z, start_pfn, end_pfn); } + +static inline bool is_shuffle_order(int order) +{ + if (!static_branch_unlikely(&page_alloc_shuffle_key)) + return false; + return order >= CONFIG_SHUFFLE_PAGE_ORDER; +} #else static inline void shuffle_free_memory(pg_data_t *pgdat, unsigned long start_pfn, unsigned long end_pfn) @@ -43,5 +50,10 @@ static inline void shuffle_zone(struct zone *z, unsigned long start_pfn, static inline void page_alloc_shuffle(void) { } + +static inline bool is_shuffle_order(int order) +{ + return false; +} #endif #endif /* _MM_SHUFFLE_H */ diff --git a/mm/page_alloc.c b/mm/page_alloc.c index de8b5eb78d13..3a932ba23daf 100644 --- a/mm/page_alloc.c +++ b/mm/page_alloc.c @@ -42,6 +42,7 @@ #include #include #include +#include #include #include #include @@ -851,7 +852,8 @@ static inline void __free_one_page(struct page *page, * so it's less likely to be used soon and more likely to be merged * as a higher order page */ - if ((order < MAX_ORDER-2) && pfn_valid_within(buddy_pfn)) { + if ((order < MAX_ORDER-2) && pfn_valid_within(buddy_pfn) + && !is_shuffle_order(order)) { struct page *higher_page, *higher_buddy; combined_pfn = buddy_pfn & pfn; higher_page = page + (combined_pfn - pfn); @@ -865,7 +867,12 @@ static inline void __free_one_page(struct page *page, } } - add_to_free_area(page, &zone->free_area[order], migratetype); + if (is_shuffle_order(order)) + add_to_free_area_random(page, &zone->free_area[order], + migratetype); + else + add_to_free_area(page, &zone->free_area[order], migratetype); + } /* diff --git a/mm/shuffle.c b/mm/shuffle.c index 07961ff41a03..4cadf51c9b40 100644 --- a/mm/shuffle.c +++ b/mm/shuffle.c @@ -213,3 +213,19 @@ void __meminit __shuffle_free_memory(pg_data_t *pgdat, unsigned long start_pfn, for (z = pgdat->node_zones; z < pgdat->node_zones + MAX_NR_ZONES; z++) shuffle_zone(z, start_pfn, end_pfn); } + +void add_to_free_area_random(struct page *page, struct free_area *area, + int migratetype) +{ + if (area->rand_bits == 0) { + area->rand_bits = 64; + area->rand = get_random_u64(); + } + + if (area->rand & 1) + add_to_free_area(page, area, migratetype); + else + add_to_free_area_tail(page, area, migratetype); + area->rand_bits--; + area->rand >>= 1; +}