From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pf1-f198.google.com (mail-pf1-f198.google.com [209.85.210.198]) by kanga.kvack.org (Postfix) with ESMTP id A40728E0038 for ; Mon, 7 Jan 2019 18:33:59 -0500 (EST) Received: by mail-pf1-f198.google.com with SMTP id p15so1322520pfk.7 for ; Mon, 07 Jan 2019 15:33:59 -0800 (PST) Received: from mga01.intel.com (mga01.intel.com. [192.55.52.88]) by mx.google.com with ESMTPS id x64si8003259pfx.87.2019.01.07.15.33.58 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 07 Jan 2019 15:33:58 -0800 (PST) Subject: [PATCH v7 3/3] mm: Maintain randomization of page free lists From: Dan Williams Date: Mon, 07 Jan 2019 15:21:21 -0800 Message-ID: <154690328135.676627.5979130839159447106.stgit@dwillia2-desk3.amr.corp.intel.com> In-Reply-To: <154690326478.676627.103843791978176914.stgit@dwillia2-desk3.amr.corp.intel.com> References: <154690326478.676627.103843791978176914.stgit@dwillia2-desk3.amr.corp.intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: akpm@linux-foundation.org Cc: Michal Hocko , Kees Cook , Dave Hansen mhocko@suse.com, keith.busch@intel.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org, mgorman@suse.de 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 b78a45e0b11c..c15f7f703be0 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 d109161f4a62..85b7f5f32867 100644 --- a/include/linux/shuffle.h +++ b/include/linux/shuffle.h @@ -30,6 +30,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) @@ -44,5 +51,10 @@ static inline void shuffle_zone(struct zone *z, unsigned long start_pfn, static inline void page_alloc_shuffle(enum mm_shuffle_ctl ctl) { } + +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 0b4791a2dd43..f3a859b66d70 100644 --- a/mm/page_alloc.c +++ b/mm/page_alloc.c @@ -43,6 +43,7 @@ #include #include #include +#include #include #include #include @@ -889,7 +890,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); @@ -903,7 +905,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; +} 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=-7.0 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY,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 AF623C43387 for ; Mon, 7 Jan 2019 23:34:00 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 7457E2070B for ; Mon, 7 Jan 2019 23:34:00 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 7457E2070B Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=intel.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 0221E8E0045; Mon, 7 Jan 2019 18:34:00 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id F13378E0038; Mon, 7 Jan 2019 18:33:59 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E2A848E0045; Mon, 7 Jan 2019 18:33:59 -0500 (EST) 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 A40728E0038 for ; Mon, 7 Jan 2019 18:33:59 -0500 (EST) Received: by mail-pf1-f198.google.com with SMTP id p15so1322520pfk.7 for ; Mon, 07 Jan 2019 15:33:59 -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=D6R2d8jUdCA20oSwfq2pCDQChznk2D94CBWykdCqt8A=; b=aIAcVoOgwTWUTmsjCtmwwtorWHfCP9OaqhPebfDsXM2RmDsLrxagS5b/hud6UawQtn 9fnP3+JlL5w3A0HcRHT5wjwFmHuiRJgbnebDzL+RP5uGxyvmikTVb5FMGrOhwFcvfqfh XIE3MXg1poB4i/gAxjQ/TAY1Up328QbW75SjKOZqckvtSjrCB3NwwRaN27E0YUq7UZv4 qQSJxyYInWCAlKyTJ304aRdCYZiNpYUXB/1v/1MF7I7qe6zN1f7PtcbARZrgJ0Ei0LQB Z3zRnQEb+em6KOdYnK8+FjbKo7xu+/wDVjvRGFDY/SCNy4Z0hRYfksmf1WmSIj3PvVU+ Ptrg== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dan.j.williams@intel.com designates 192.55.52.88 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: AJcUukcOZYc+VxcRXYblR/4BMcbR6lHexeUibLRyDLwnh/cDB75WkQ4I QZCYi/vSbvmmko/Hlf8yVtMI+mNlVxzTXNE1g+vyeVV8Ty6xeFfHTax4jvE1qrwTTec+ey33UMD D06A0+1NZF4RobRlCmNkO1adY+2Jm83x6QQ1f+xcF4n9sSrQT8xPCi/nnzERzyFp4zA== X-Received: by 2002:a63:de46:: with SMTP id y6mr12563388pgi.198.1546904039308; Mon, 07 Jan 2019 15:33:59 -0800 (PST) X-Google-Smtp-Source: ALg8bN7FWMyeIzgO1Ig8wcF2fR123bFcJ4ygItULNYAAWRdKMzsyxYJSG+doPZEsUZ2URIum14+G X-Received: by 2002:a63:de46:: with SMTP id y6mr12563360pgi.198.1546904038501; Mon, 07 Jan 2019 15:33:58 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1546904038; cv=none; d=google.com; s=arc-20160816; b=jmzoyNJKPdWmM3cLTbyUw+QKMDLu6fmeSaH3uoGrlsbaupwTW6LJOwwiFzmMdcPebc zkh54gfWJRmhc+mkGLz1sp6Geh+TGAM4w+dtuw7dMHdMRtDcK/w0x/DZRYygMBjs5nK8 vfLfMJoJUyKKzTSTs+XUJUa9x4MAdsVaD3+8wdnMSY58XciVrg6snEG3RBdkJ8YiBnOT /7dk7y+yqU83WWGaal5CKoDPYTKIKaoJ3zeX+isO1zJiOE+zsNb5tlXSR1ws1749iaxd vdsmImI0lRhh/QGuy7qgj9SUYQBTlUqLY8tLYD1M6297fp0eltyr8dJPdH37vHSXnfI1 pKKA== 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=D6R2d8jUdCA20oSwfq2pCDQChznk2D94CBWykdCqt8A=; b=WPqNQfbHfE356NIZSDKcjEIFL/eRAuTewOXpDeTm60OmzYoZWnRTEJivCzRQ4ENDAm th80+hIaER6FVWsbzG7OKFHL0JWzRMI8TPhIyuTn1ZWacBihW7fF4EpqziHxFEhM56Zq QMqH0kBEPClEVODsLQlB8mwKsKpan6qTq4twltqVrM2xCMpgGeNGQnseTCVocB1DE2av GNHM7Amvtw6NBNqkSSGb4v5lHFPevT4DUiZqX7QBTl/70695VGgjtza7nI3p+JiX3yjB 7Dw5SNyO3mGzaf4Cw7MgayiVjz8fNDZ7M0ADVoHGvxkqy5+MvOlHphLaCn//+UrIpu1S LvWQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dan.j.williams@intel.com designates 192.55.52.88 as permitted sender) smtp.mailfrom=dan.j.williams@intel.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com Received: from mga01.intel.com (mga01.intel.com. [192.55.52.88]) by mx.google.com with ESMTPS id x64si8003259pfx.87.2019.01.07.15.33.58 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 07 Jan 2019 15:33:58 -0800 (PST) Received-SPF: pass (google.com: domain of dan.j.williams@intel.com designates 192.55.52.88 as permitted sender) client-ip=192.55.52.88; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dan.j.williams@intel.com designates 192.55.52.88 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 orsmga003.jf.intel.com ([10.7.209.27]) by fmsmga101.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 07 Jan 2019 15:33:58 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.56,451,1539673200"; d="scan'208";a="116258313" Received: from dwillia2-desk3.jf.intel.com (HELO dwillia2-desk3.amr.corp.intel.com) ([10.54.39.16]) by orsmga003.jf.intel.com with ESMTP; 07 Jan 2019 15:33:57 -0800 Subject: [PATCH v7 3/3] mm: Maintain randomization of page free lists From: Dan Williams To: akpm@linux-foundation.org Cc: Michal Hocko , Kees Cook , Dave Hansen , mhocko@suse.com, keith.busch@intel.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org, mgorman@suse.de Date: Mon, 07 Jan 2019 15:21:21 -0800 Message-ID: <154690328135.676627.5979130839159447106.stgit@dwillia2-desk3.amr.corp.intel.com> In-Reply-To: <154690326478.676627.103843791978176914.stgit@dwillia2-desk3.amr.corp.intel.com> References: <154690326478.676627.103843791978176914.stgit@dwillia2-desk3.amr.corp.intel.com> User-Agent: StGit/0.18-2-gc94f MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit 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: Message-ID: <20190107232121._rowH_y7rl-m5kASIpZ4cQ8pkF4KkKBeZI35vTJ5BO8@z> 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 b78a45e0b11c..c15f7f703be0 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 d109161f4a62..85b7f5f32867 100644 --- a/include/linux/shuffle.h +++ b/include/linux/shuffle.h @@ -30,6 +30,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) @@ -44,5 +51,10 @@ static inline void shuffle_zone(struct zone *z, unsigned long start_pfn, static inline void page_alloc_shuffle(enum mm_shuffle_ctl ctl) { } + +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 0b4791a2dd43..f3a859b66d70 100644 --- a/mm/page_alloc.c +++ b/mm/page_alloc.c @@ -43,6 +43,7 @@ #include #include #include +#include #include #include #include @@ -889,7 +890,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); @@ -903,7 +905,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; +}