The patch titled
Subject: mm: maintain randomization of page free lists
has been added to the -mm tree. Its filename is
mm-maintain-randomization-of-page-free-lists.patch
This patch should soon appear at
http://ozlabs.org/~akpm/mmots/broken-out/mm-maintain-randomization-of-page-free-lists.patch
and later at
http://ozlabs.org/~akpm/mmotm/broken-out/mm-maintain-randomization-of-page-free-lists.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Dan Williams <dan.j.williams@xxxxxxxxx>
Subject: mm: maintain randomization of page free lists
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.
Link: http://lkml.kernel.org/r/154899812788.3165233.9066631950746578517.stgit@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Signed-off-by: Dan Williams <dan.j.williams@xxxxxxxxx>
Reviewed-by: Kees Cook <keescook@xxxxxxxxxxxx>
Cc: Michal Hocko <mhocko@xxxxxxxx>
Cc: Dave Hansen <dave.hansen@xxxxxxxxxxxxxxx>
Cc: https://lkml.kernel.org/r/AT5PR8401MB1169D656C8B5E121752FC0F8AB120@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Cc: Keith Busch <keith.busch@xxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
include/linux/mmzone.h | 12 ++++++++++++
mm/page_alloc.c | 11 +++++++++--
mm/shuffle.c | 23 +++++++++++++++++++++++
mm/shuffle.h | 12 ++++++++++++
4 files changed, 56 insertions(+), 2 deletions(-)
--- a/include/linux/mmzone.h~mm-maintain-randomization-of-page-free-lists
+++ a/include/linux/mmzone.h
@@ -116,6 +116,18 @@ static inline void add_to_free_area_tail
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
+static inline void add_to_free_area_random(struct page *page,
+ struct free_area *area, int migratetype)
+{
+ add_to_free_area(page, area, migratetype);
+}
+#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)
--- a/mm/page_alloc.c~mm-maintain-randomization-of-page-free-lists
+++ a/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>
@@ -946,7 +947,8 @@ done_merging:
* 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);
@@ -960,7 +962,12 @@ done_merging:
}
}
- 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);
+
}
/*
--- a/mm/shuffle.c~mm-maintain-randomization-of-page-free-lists
+++ a/mm/shuffle.c
@@ -168,3 +168,26 @@ void __meminit __shuffle_free_memory(pg_
for (z = pgdat->node_zones; z < pgdat->node_zones + MAX_NR_ZONES; z++)
shuffle_zone(z);
}
+
+void add_to_free_area_random(struct page *page, struct free_area *area,
+ int migratetype)
+{
+ static u64 rand;
+ static u8 rand_bits;
+
+ /*
+ * The lack of locking is deliberate. If 2 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 (rand & 1)
+ add_to_free_area(page, area, migratetype);
+ else
+ add_to_free_area_tail(page, area, migratetype);
+ rand_bits--;
+ rand >>= 1;
+}
--- a/mm/shuffle.h~mm-maintain-randomization-of-page-free-lists
+++ a/mm/shuffle.h
@@ -36,6 +36,13 @@ static inline void shuffle_zone(struct z
return;
__shuffle_zone(z);
}
+
+static inline bool is_shuffle_order(int order)
+{
+ if (!static_branch_unlikely(&page_alloc_shuffle_key))
+ return false;
+ return order >= SHUFFLE_ORDER;
+}
#else
static inline void shuffle_free_memory(pg_data_t *pgdat)
{
@@ -48,5 +55,10 @@ static inline void shuffle_zone(struct z
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 */
_
Patches currently in -mm which might be from dan.j.williams@xxxxxxxxx are
mm-shuffle-initial-free-memory-to-improve-memory-side-cache-utilization.patch
mm-move-buddy-list-manipulations-into-helpers.patch
mm-maintain-randomization-of-page-free-lists.patch
