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