From: Dan Williams <dan.j.williams@intel.com> To: akpm@linux-foundation.org Cc: Michal Hocko <mhocko@suse.com>, Kees Cook <keescook@chromium.org>, Dave Hansen <dave.hansen@linux.intel.com>, linux-mm@kvack.org, linux-kernel@vger.kernel.org, keescook@chromium.org Subject: [PATCH v2 3/3] mm: Maintain randomization of page free lists Date: Wed, 03 Oct 2018 19:15:34 -0700 [thread overview] Message-ID: <153861933441.2863953.2686611248399177664.stgit@dwillia2-desk3.amr.corp.intel.com> (raw) In-Reply-To: <153861931865.2863953.11185006931458762795.stgit@dwillia2-desk3.amr.corp.intel.com> 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 <mhocko@suse.com> Cc: Kees Cook <keescook@chromium.org> Cc: Dave Hansen <dave.hansen@linux.intel.com> Signed-off-by: Dan Williams <dan.j.williams@intel.com> --- include/linux/mmzone.h | 2 ++ mm/page_alloc.c | 27 +++++++++++++++++++++++++-- 2 files changed, 27 insertions(+), 2 deletions(-) diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h index adf9b3a7440d..4a095432843d 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 */ diff --git a/mm/page_alloc.c b/mm/page_alloc.c index b4a1598fcab5..e659119351ad 100644 --- a/mm/page_alloc.c +++ b/mm/page_alloc.c @@ -43,6 +43,7 @@ #include <linux/mempolicy.h> #include <linux/memremap.h> #include <linux/stop_machine.h> +#include <linux/random.h> #include <linux/sort.h> #include <linux/pfn.h> #include <linux/backing-dev.h> @@ -746,6 +747,22 @@ static inline int page_is_buddy(struct page *page, struct page *buddy, return 0; } +static 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; +} + /* * Freeing function for a buddy system allocator. * @@ -851,7 +868,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) + && order < shuffle_page_order) { struct page *higher_page, *higher_buddy; combined_pfn = buddy_pfn & pfn; higher_page = page + (combined_pfn - pfn); @@ -865,7 +883,12 @@ static inline void __free_one_page(struct page *page, } } - add_to_free_area(page, &zone->free_area[order], migratetype); + if (order < shuffle_page_order) + add_to_free_area(page, &zone->free_area[order], migratetype); + else + add_to_free_area_random(page, &zone->free_area[order], + migratetype); + } /*
WARNING: multiple messages have this Message-ID (diff)
From: Dan Williams <dan.j.williams@intel.com> To: akpm@linux-foundation.org Cc: Michal Hocko <mhocko@suse.com>, Kees Cook <keescook@chromium.org>, Dave Hansen <dave.hansen@linux.intel.com>, linux-mm@kvack.org, linux-kernel@vger.kernel.orgkeescook@chromium.org Subject: [PATCH v2 3/3] mm: Maintain randomization of page free lists Date: Wed, 03 Oct 2018 19:15:34 -0700 [thread overview] Message-ID: <153861933441.2863953.2686611248399177664.stgit@dwillia2-desk3.amr.corp.intel.com> (raw) In-Reply-To: <153861931865.2863953.11185006931458762795.stgit@dwillia2-desk3.amr.corp.intel.com> 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 <mhocko@suse.com> Cc: Kees Cook <keescook@chromium.org> Cc: Dave Hansen <dave.hansen@linux.intel.com> Signed-off-by: Dan Williams <dan.j.williams@intel.com> --- include/linux/mmzone.h | 2 ++ mm/page_alloc.c | 27 +++++++++++++++++++++++++-- 2 files changed, 27 insertions(+), 2 deletions(-) diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h index adf9b3a7440d..4a095432843d 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 */ diff --git a/mm/page_alloc.c b/mm/page_alloc.c index b4a1598fcab5..e659119351ad 100644 --- a/mm/page_alloc.c +++ b/mm/page_alloc.c @@ -43,6 +43,7 @@ #include <linux/mempolicy.h> #include <linux/memremap.h> #include <linux/stop_machine.h> +#include <linux/random.h> #include <linux/sort.h> #include <linux/pfn.h> #include <linux/backing-dev.h> @@ -746,6 +747,22 @@ static inline int page_is_buddy(struct page *page, struct page *buddy, return 0; } +static 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; +} + /* * Freeing function for a buddy system allocator. * @@ -851,7 +868,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) + && order < shuffle_page_order) { struct page *higher_page, *higher_buddy; combined_pfn = buddy_pfn & pfn; higher_page = page + (combined_pfn - pfn); @@ -865,7 +883,12 @@ static inline void __free_one_page(struct page *page, } } - add_to_free_area(page, &zone->free_area[order], migratetype); + if (order < shuffle_page_order) + add_to_free_area(page, &zone->free_area[order], migratetype); + else + add_to_free_area_random(page, &zone->free_area[order], + migratetype); + } /*
next prev parent reply other threads:[~2018-10-04 2:29 UTC|newest] Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top 2018-10-04 2:15 [PATCH v2 0/3] Randomize free memory Dan Williams 2018-10-04 2:15 ` Dan Williams 2018-10-04 2:15 ` [PATCH v2 1/3] mm: Shuffle initial " Dan Williams 2018-10-04 2:15 ` Dan Williams 2018-10-04 7:48 ` Michal Hocko 2018-10-04 16:51 ` Dan Williams 2018-10-09 11:12 ` Michal Hocko 2018-10-09 17:36 ` Dan Williams 2018-10-04 2:15 ` [PATCH v2 2/3] mm: Move buddy list manipulations into helpers Dan Williams 2018-10-04 2:15 ` Dan Williams [this message] 2018-10-04 2:15 ` [PATCH v2 3/3] mm: Maintain randomization of page free lists Dan Williams 2018-10-04 7:44 ` [PATCH v2 0/3] Randomize free memory Michal Hocko 2018-10-04 16:44 ` Dan Williams 2018-10-06 17:01 ` Dan Williams 2018-10-09 11:22 ` Michal Hocko 2018-10-09 17:34 ` Dan Williams 2018-10-10 8:47 ` Michal Hocko 2018-10-11 0:13 ` Dan Williams 2018-10-11 11:52 ` Michal Hocko 2018-10-11 18:03 ` Dan Williams 2018-10-18 13:44 ` Michal Hocko 2018-10-12 8:22 ` Mel Gorman
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=153861933441.2863953.2686611248399177664.stgit@dwillia2-desk3.amr.corp.intel.com \ --to=dan.j.williams@intel.com \ --cc=akpm@linux-foundation.org \ --cc=dave.hansen@linux.intel.com \ --cc=keescook@chromium.org \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=mhocko@suse.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.