Blame view
mm/shuffle.c
4.68 KB
e900a918b mm: shuffle initi... |
1 2 3 4 5 6 7 8 9 10 11 12 |
// SPDX-License-Identifier: GPL-2.0 // Copyright(c) 2018 Intel Corporation. All rights reserved. #include <linux/mm.h> #include <linux/init.h> #include <linux/mmzone.h> #include <linux/random.h> #include <linux/moduleparam.h> #include "internal.h" #include "shuffle.h" DEFINE_STATIC_KEY_FALSE(page_alloc_shuffle_key); |
e900a918b mm: shuffle initi... |
13 14 |
static bool shuffle_param; |
758b8db4a mm: fix -Wmissing... |
15 |
static int shuffle_show(char *buffer, const struct kernel_param *kp) |
e900a918b mm: shuffle initi... |
16 |
{ |
839195352 mm/shuffle: remov... |
17 18 |
return sprintf(buffer, "%c ", shuffle_param ? 'Y' : 'N'); |
e900a918b mm: shuffle initi... |
19 20 21 22 23 24 25 26 27 28 |
} static __meminit int shuffle_store(const char *val, const struct kernel_param *kp) { int rc = param_set_bool(val, kp); if (rc < 0) return rc; if (shuffle_param) |
839195352 mm/shuffle: remov... |
29 |
static_branch_enable(&page_alloc_shuffle_key); |
e900a918b mm: shuffle initi... |
30 31 32 33 34 35 36 37 |
return 0; } module_param_call(shuffle, shuffle_store, shuffle_show, &shuffle_param, 0400); /* * For two pages to be swapped in the shuffle, they must be free (on a * 'free_area' lru), have the same order, and have the same migratetype. */ |
4a93025cb mm/shuffle: don't... |
38 39 |
static struct page * __meminit shuffle_valid_page(struct zone *zone, unsigned long pfn, int order) |
e900a918b mm: shuffle initi... |
40 |
{ |
4a93025cb mm/shuffle: don't... |
41 |
struct page *page = pfn_to_online_page(pfn); |
e900a918b mm: shuffle initi... |
42 43 44 45 46 |
/* * Given we're dealing with randomly selected pfns in a zone we * need to ask questions like... */ |
4a93025cb mm/shuffle: don't... |
47 48 |
/* ... is the page managed by the buddy? */ if (!page) |
e900a918b mm: shuffle initi... |
49 |
return NULL; |
4a93025cb mm/shuffle: don't... |
50 51 |
/* ... is the page assigned to the same zone? */ if (page_zone(page) != zone) |
e900a918b mm: shuffle initi... |
52 53 54 |
return NULL; /* ...is the page free and currently on a free_area list? */ |
e900a918b mm: shuffle initi... |
55 56 57 58 59 60 61 |
if (!PageBuddy(page)) return NULL; /* * ...is the page on the same list as the page we will * shuffle it with? */ |
ab130f910 mm: rename page_o... |
62 |
if (buddy_order(page) != order) |
e900a918b mm: shuffle initi... |
63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
return NULL; return page; } /* * Fisher-Yates shuffle the freelist which prescribes iterating through an * array, pfns in this case, and randomly swapping each entry with another in * the span, end_pfn - start_pfn. * * To keep the implementation simple it does not attempt to correct for sources * of bias in the distribution, like modulo bias or pseudo-random number * generator bias. I.e. the expectation is that this shuffling raises the bar * for attacks that exploit the predictability of page allocations, but need not * be a perfect shuffle. */ #define SHUFFLE_RETRY 10 void __meminit __shuffle_zone(struct zone *z) { unsigned long i, flags; unsigned long start_pfn = z->zone_start_pfn; unsigned long end_pfn = zone_end_pfn(z); const int order = SHUFFLE_ORDER; const int order_pages = 1 << order; spin_lock_irqsave(&z->lock, flags); start_pfn = ALIGN(start_pfn, order_pages); for (i = start_pfn; i < end_pfn; i += order_pages) { unsigned long j; int migratetype, retry; struct page *page_i, *page_j; /* * We expect page_i, in the sub-range of a zone being added * (@start_pfn to @end_pfn), to more likely be valid compared to * page_j randomly selected in the span @zone_start_pfn to * @spanned_pages. */ |
4a93025cb mm/shuffle: don't... |
101 |
page_i = shuffle_valid_page(z, i, order); |
e900a918b mm: shuffle initi... |
102 103 104 105 106 107 108 109 110 111 112 113 114 |
if (!page_i) continue; for (retry = 0; retry < SHUFFLE_RETRY; retry++) { /* * Pick a random order aligned page in the zone span as * a swap target. If the selected pfn is a hole, retry * up to SHUFFLE_RETRY attempts find a random valid pfn * in the zone. */ j = z->zone_start_pfn + ALIGN_DOWN(get_random_long() % z->spanned_pages, order_pages); |
4a93025cb mm/shuffle: don't... |
115 |
page_j = shuffle_valid_page(z, j, order); |
e900a918b mm: shuffle initi... |
116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 |
if (page_j && page_j != page_i) break; } if (retry >= SHUFFLE_RETRY) { pr_debug("%s: failed to swap %#lx ", __func__, i); continue; } /* * Each migratetype corresponds to its own list, make sure the * types match otherwise we're moving pages to lists where they * do not belong. */ migratetype = get_pageblock_migratetype(page_i); if (get_pageblock_migratetype(page_j) != migratetype) { pr_debug("%s: migratetype mismatch %#lx ", __func__, i); continue; } list_swap(&page_i->lru, &page_j->lru); pr_debug("%s: swap: %#lx -> %#lx ", __func__, i, j); /* take it easy on the zone lock */ if ((i % (100 * order_pages)) == 0) { spin_unlock_irqrestore(&z->lock, flags); cond_resched(); spin_lock_irqsave(&z->lock, flags); } } spin_unlock_irqrestore(&z->lock, flags); } /** * shuffle_free_memory - reduce the predictability of the page allocator * @pgdat: node page data */ void __meminit __shuffle_free_memory(pg_data_t *pgdat) { struct zone *z; for (z = pgdat->node_zones; z < pgdat->node_zones + MAX_NR_ZONES; z++) shuffle_zone(z); } |
97500a4a5 mm: maintain rand... |
163 |
|
a2129f247 mm: adjust shuffl... |
164 |
bool shuffle_pick_tail(void) |
97500a4a5 mm: maintain rand... |
165 166 167 |
{ static u64 rand; static u8 rand_bits; |
a2129f247 mm: adjust shuffl... |
168 |
bool ret; |
97500a4a5 mm: maintain rand... |
169 170 171 172 173 174 175 176 177 |
/* * 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(); } |
a2129f247 mm: adjust shuffl... |
178 |
ret = rand & 1; |
97500a4a5 mm: maintain rand... |
179 180 |
rand_bits--; rand >>= 1; |
a2129f247 mm: adjust shuffl... |
181 182 |
return ret; |
97500a4a5 mm: maintain rand... |
183 |
} |