From patchwork Wed Jan 16 22:57:52 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dan Williams X-Patchwork-Id: 10767099 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 6E90C13A4 for ; Wed, 16 Jan 2019 23:10:34 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 5EA5F2FB4C for ; Wed, 16 Jan 2019 23:10:34 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 52D902FB88; Wed, 16 Jan 2019 23:10:34 +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 1F7142FB83 for ; Wed, 16 Jan 2019 23:10:33 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DCE498E0007; Wed, 16 Jan 2019 18:10:31 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id D58818E0002; Wed, 16 Jan 2019 18:10:31 -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 C469B8E0007; Wed, 16 Jan 2019 18:10:31 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-pg1-f199.google.com (mail-pg1-f199.google.com [209.85.215.199]) by kanga.kvack.org (Postfix) with ESMTP id 82FE88E0002 for ; Wed, 16 Jan 2019 18:10:31 -0500 (EST) Received: by mail-pg1-f199.google.com with SMTP id u17so4851075pgn.17 for ; Wed, 16 Jan 2019 15:10:31 -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=e0pw4178hg7uJLQytdJ7YJ0mW45d1oixb/rjPSVcRLI=; b=mbsXavOVaLyPRjA0m9HVlv5ZVXFij3Ls5/j947hEESS5x8HGOekaSO0cgSqVekDVF5 XerCchjFTJt77t0gpf1Tx5mi/lKDjr2GysScPi9laopFb4CsNOkvHwBlyspCh8cQ2Q2c coad5Ml0cA4N0poT9gumJtGOWmK3LZOO3ntQ6eI4oSZ8Z6ftbuTHSJs2BIkxMYlVE5kL sm5K9kgSD8W89pnGm4o4FG3+Z7XH3fnLpRBX057l1U2U+dFONSA7DAy2jmTecvduOFKt AxlGbyZ5csGG2osj9aD76CuqD5uwEGAePDO3a0T5ErjWO5aytH7/RlkNCtGrs1KuHYxM drSA== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dan.j.williams@intel.com designates 192.55.52.136 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: AJcUukeBnTByv5/qPPpQtICvzGl3Fi5hqhKx1ZrTFkjAe2dhePbOo32o lBOOPgCEUOznr1xNuOkUyAwm3+rqC6dTdPJY4kT+SIFLmaZshgUVH8PT3gEIdSyLxx6pTwAr0O1 thrTqoZewsWATnUrrGOJwVDLdhbUb9jjN4IL/UPb5G9MTiuDo2P+Jl6hVKzp5L6ZI7A== X-Received: by 2002:a17:902:e012:: with SMTP id ca18mr12371568plb.218.1547680231108; Wed, 16 Jan 2019 15:10:31 -0800 (PST) X-Google-Smtp-Source: ALg8bN6ehx61Ax9S6tZlGemff/VLHFY9FdBFPhhwNy4WxDI2XG4r3bYmF8vUg1ISuY4ZOIRsjGnG X-Received: by 2002:a17:902:e012:: with SMTP id ca18mr12371504plb.218.1547680230264; Wed, 16 Jan 2019 15:10:30 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1547680230; cv=none; d=google.com; s=arc-20160816; b=mopz4sjfzniNVTL1ALx+7nCcaEY69SqrYX3jytQiCjItzrC+9qKqniRbr1zzu5cuWq mlGhtwdtbOjypyut+zw86icaZMjCLhY5ySkTDCp/E25olJW9h9FpMwAXGSzYOO2hzwcm ZvrhtTqNODGNJyHnTg74Jz9FXWAvzj+51d4lIlp7wV6v59adRd3S2/UAXxvNPkHHIC5L Zdil4vN9w1smTLo8UW9cRogyO+uAkmDH16WljoasmfDgAASCn54jXuxxi8MWxGvX9wDs qXrJ1DcYeEJZxmZ9O2pcOfBoX8fxIkFJxf+T6Xwn4Gz0IBfyWBcUUo35JNCaymOZt1FQ sSmw== 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=e0pw4178hg7uJLQytdJ7YJ0mW45d1oixb/rjPSVcRLI=; b=PEG+5mQlw2FhBDCM+TD521EH1PzlRVQ9MB+B6jvUHDU5us+UPl8FCkPvQz/QOkxh4r A1cD7xnlaRLyXwtdtG3dJ+qMW/uYOZIl/q70yOd8P680tp/oh8cT737ORDQGkQIHOxSj MMV7uX3ErrNbsdzgDiEVxGJPeaGhIeaBmnwx0rC7mNCkqHhkhkcJExi056/xKKZOsSA2 KyOG7wJFxjSCGW+3Sv6uETO3wpziUrAvgSdDtCUAOKDL00uJ7mfciMVFkII05N0JOJIZ 6tIsQPP0YExRDCcPO3OwO8BHtDH7iWwbgaPV93kS0XANUffIBhJy3O8/SixQzRif7Cui nvUw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dan.j.williams@intel.com designates 192.55.52.136 as permitted sender) smtp.mailfrom=dan.j.williams@intel.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com Received: from mga12.intel.com (mga12.intel.com. [192.55.52.136]) by mx.google.com with ESMTPS id v7si6529157pgs.304.2019.01.16.15.10.30 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 16 Jan 2019 15:10:30 -0800 (PST) Received-SPF: pass (google.com: domain of dan.j.williams@intel.com designates 192.55.52.136 as permitted sender) client-ip=192.55.52.136; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dan.j.williams@intel.com designates 192.55.52.136 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 fmsmga006.fm.intel.com ([10.253.24.20]) by fmsmga106.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 16 Jan 2019 15:10:29 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.56,487,1539673200"; d="scan'208";a="311045123" Received: from dwillia2-desk3.jf.intel.com (HELO dwillia2-desk3.amr.corp.intel.com) ([10.54.39.16]) by fmsmga006.fm.intel.com with ESMTP; 16 Jan 2019 15:10:29 -0800 Subject: [PATCH v8 3/3] mm: Maintain randomization of page free lists From: Dan Williams To: akpm@linux-foundation.org Cc: Michal Hocko , Dave Hansen , Kees Cook , linux-mm@kvack.org, linux-kernel@vger.kernel.org, keith.busch@intel.com Date: Wed, 16 Jan 2019 14:57:52 -0800 Message-ID: <154767947255.1983228.16850950514476882424.stgit@dwillia2-desk3.amr.corp.intel.com> In-Reply-To: <154767945660.1983228.12167020940431682725.stgit@dwillia2-desk3.amr.corp.intel.com> References: <154767945660.1983228.12167020940431682725.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: Dave Hansen Reviewed-by: Kees Cook 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 5d39e8cb50f7..c09d5e56f5c4 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; +}